Сегментация текста: разбиение слов на основе словаря

Задний план

Разделите имена столбцов базы данных на эквивалентный текст на английском языке, чтобы заполнить словарь данных. Словарь английского языка создан на основе корпоративных документов, вики-сайтов и электронной почты. Словарь (lexicon.csv) представляет собой файл CSV со словами и вероятностями. Таким образом, чем чаще кто-то пишет слово «терапевт» (в электронной почте или на вики-странице), тем выше вероятность того, что «имя терапевта» разделится на «имя терапевта», а не на что-то другое. (Скорее всего, в лексикон даже не войдет слово «насильник».)

Исходный код

• TextSegmenter.java @ http://pastebin.com/taXyE03L
• SortableValueMap.java @ http://pastebin.com/v3hRXYan

Дата файлы

• lexicon.csv — http://pastebin.com/0crECtXY
• columns.txt – http://pastebin.com/EtN9Qesr

Проблема (обновлено 03 января 2011 г.)

Когда возникает следующая проблема:

dependentrelationship::end depend ent dependent relationship
end=0.86
ent=0.001
dependent=0.8
relationship=0.9

Существуют следующие возможные решения:

dependentrelationship::dependent relationship
dependentrelationship::dep end ent relationship
dependentrelationship::depend ent relationship

Лексикон содержит слова с их относительными вероятностями (в зависимости от частоты слов): dependent 0.8, end 0.86, relationship 0.9, depend 0.3 и ent 0.001.

Исключите решение dep end ent relationship, потому что dep отсутствует в лексиконе (т. е. используется 75% слов), тогда как два других решения охватывают 100% слов в лексиконе. Из оставшихся решений вероятность dependent relationship составляет 0,72, тогда как вероятность depend ent relationship составляет 0,00027. Поэтому мы можем выбрать dependent relationship как правильное решение.

Связанный

• Как разделить слова в предложении пробелами?
• Top Coder — Презентация сегментации текста 1/2
• Top Coder — Презентация сегментации текста 2 / 2
• Сегментация линейного текста с использованием алгоритма динамического программирования
• Динамическое программирование: сегментация
• Динамическое программирование: вычислительный инструмент

Вопрос

Данный:

// The concatenated phrase or database column (e.g., dependentrelationship).
String concat;

// All words (String) in the lexicon within concat, in left-to-right order; and
// the ranked probability of those words (Double). (E.g., {end, 0.97}
// {dependent, 0.86}, {relationship, 0.95}.)
Map.Entry<String, Double> word;

Как бы вы реализовали подпрограмму, которая генерирует наиболее вероятное решение на основе охвата словарного запаса и вероятностей? Например:

for( Map.Entry<String, Double> word : words ) {
  result.append( word.getKey() ).append( ' ' );

  // What goes here?

  System.out.printf( "%s=%f\n", word.getKey(), word.getValue() );
}

Спасибо!