Нужна помощь в понимании этого алгоритма Python Viterbi

Я пытаюсь преобразовать реализацию Python алгоритма Витерби, найденную в этом ответе на переполнение стека, в Ruby. Полный сценарий можно найти внизу этого вопроса с моими комментариями.

К сожалению, я очень мало знаю о Python, поэтому перевод оказался сложнее, чем хотелось бы. Тем не менее, я добился некоторого прогресса. Прямо сейчас единственная строчка, которая полностью расплавляет мой мозг, это:

prob_k, k = max((probs[j] * word_prob(text[j:i]), j) for j in range(max(0, i - max_word_length), i))

Может кто-нибудь объяснить, что он делает?

Вот полный скрипт Python:

import re
from itertools import groupby

# text will be a compound word such as 'wickedweather'.
def viterbi_segment(text):
  probs, lasts = [1.0], [0]

  # Iterate over the letters in the compound.
  # eg. [w, ickedweather], [wi, ckedweather], and so on.
  for i in range(1, len(text) + 1):
    # I've no idea what this line is doing and I can't figure out how to split it up?
    prob_k, k = max((probs[j] * word_prob(text[j:i]), j) for j in range(max(0, i - max_word_length), i))
    # Append values to arrays.
    probs.append(prob_k)
    lasts.append(k)

  words = []
  i = len(text)
  while 0 < i:
    words.append(text[lasts[i]:i])
    i = lasts[i]
  words.reverse()
  return words, probs[-1]

# Calc the probability of a word based on occurrences in the dictionary.
def word_prob(word):
  # dictionary.get(key) will return the value for the specified key.
  # In this case, thats the number of occurances of thw word in the
  # dictionary. The second argument is a default value to return if
  # the word is not found.
  return dictionary.get(word, 0) / total

# This ensures we ony deal with full words rather than each
# individual letter. Normalize the words basically.
def words(text):
  return re.findall('[a-z]+', text.lower())

# This gets us a hash where the keys are words and the values are the
# number of ocurrances in the dictionary.
dictionary = dict((w, len(list(ws)))
  # /usr/share/dixt/words is a file of newline delimitated words.
  for w, ws in groupby(sorted(words(open('/usr/share/dict/words').read()))))

# Assign the length of the longest word in the dictionary.
max_word_length = max(map(len, dictionary))

# Assign the total number of words in the dictionary. It's a float
# because we're going to divide by it later on.
total = float(sum(dictionary.values()))

# Run the algo over a file of newline delimited compound words.
compounds = words(open('compounds.txt').read())
for comp in compounds:
  print comp, ": ", viterbi_segment(comp)

python viterbi
person David Tuite    schedule 12.07.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Вы просматриваете понимание списков.

Расширенная версия выглядит примерно так:

all_probs = []

for j in range(max(0, i - max_word_length), i):
    all_probs.append((probs[j] * word_prob(text[j:i]), j))

prob_k, k = max(all_probs)

Я надеюсь, что это поможет объяснить это. Если это не так, не стесняйтесь редактировать свой вопрос и указывать на утверждения, которые вы не понимаете.

person Otto Allmendinger    schedule 12.07.2012

arrow_upward
0
arrow_downward

Вот рабочая реализация ruby ​​на всякий случай, если кому-то еще она пригодится. Я перевел понимание списка, обсуждавшееся выше, в то, что я считаю подходящим уровнем идиоматически нечитаемого рубина.

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

Основным раздражением были разные определения диапазона в python и ruby ​​(открытый/закрытый интервал). Алгоритм очень быстрый.

Может оказаться выгодным работать с правдоподобием, а не с вероятностью, поскольку повторное умножение может привести к потере значимости и/или накоплению неточностей с плавающей запятой для более длинных слов.

person Matthias Winkelmann    schedule 11.10.2018