<p>这里有一个工作的ruby实现,以防其他人也能使用它。我翻译了上面讨论的列表理解,我认为这是不可读的ruby的适当级别。在</p>
<pre><code>def viterbi(text)
probabilities = [1.0]
lasts = [0]
# Iterate over the letters in the compound.
# eg. [h ellodarkness],[he llodarkness],...
(1..(text.length + 1)).each do |i|
prob_k, k = ([0, i - maximum_word_length].max...i).map { |j| [probabilities[j] * word_probability(text[j...i]), j] }.map { |s| s }.max_by(&:first)
probabilities << prob_k
lasts << k
end
words = []
i = text.length
while i.positive?
words << text[lasts[i]...i]
i = lasts[i]
end
words.reverse!
[words, probabilities.last]
end
def word_probability(word)
word_counts[word].to_f / word_counts_sum.to_f
end
def word_counts_sum
@word_counts_sum ||= word_counts.values.sum.to_f
end
def maximum_word_length
@maximum_word_length ||= word_counts.keys.map(&:length).max
end
def word_counts
return @word_counts if @word_counts
@word_counts = {"hello" => 12, "darkness" => 6, "friend" => 79, "my" => 1, "old" => 5}
@word_counts.default = 0
@word_counts
end
puts "Best split is %s with probability %.6f" % viterbi("hellodarknessmyoldfriend")
=> Best split is ["hello", "darkness", "my", "old", "friend"] with probability 0.000002
</code></pre>
<p>主要的麻烦是python和ruby(open/closed interval)中不同的范围定义。这个算法非常快。在</p>
<p>使用可能性而不是概率可能会比较有利,因为重复的乘法可能会导致下溢和/或用较长的单词累积浮点错误。在</p>