Как найти правильные слова в длинном потоке символов?
Вход :
"The revised report onthesyntactictheoriesofsequentialcontrolandstate"
Вывод Google:
"The revised report on syntactic theories sequential controlandstate"
(что достаточно близко, учитывая время, которое они произвели на выходе)
Как вы думаете, как это делает Google? Как бы вы повысили точность?
Я бы попробовал рекурсивный алгоритм следующим образом:
Например, если указать «thesentenceisgood», будет работать:
thesentenceisgood
the sentenceisgood
sent enceisgood
enceisgood: OUT1: the sent enceisgood, 2/3
sentence isgood
is good
go od: OUT2: the sentence is go od, 4/5
is good: OUT3: the sentence is good, 4/4
sentenceisgood: OUT4: the sentenceisgood, 1/2
these ntenceisgood
ntenceisgood: OUT5: these ntenceisgood, 1/2
Таким образом, вы бы выбрали OUT3 в качестве ответа.
Попробуйте стохастическую регулярную грамматику (эквивалентную скрытым марковским моделям) со следующими правилами:
for every word in a dictionary:
stream -> word_i stream with probability p_w
word_i -> letter_i1 ...letter_in` with probability q_w (this is the spelling of word_i)
stream -> letter stream with prob p (for any letter)
stream -> epsilon with prob 1
Вероятности могут быть получены из обучающего набора, но см. следующее обсуждение. Наиболее вероятный синтаксический анализ вычисляется с использованием алгоритма Витерби, который имеет квадратичную временную сложность по количеству скрытых состояний, в данном случае вашего словаря, поэтому вы можете столкнуться с проблемами скорости с большими словарями. Но что, если вы установите все p_w = 1, q_w = 1 p = 0,5, что означает, что это вероятности в модели искусственного языка, где все слова равновероятны, а все не-слова одинаково маловероятны. Конечно, вы могли бы лучше сегментировать, если бы не использовали это упрощение, но сложность алгоритма значительно снизилась. Если вы посмотрите на рекуррентное отношение в записи в Википедии, вы можете попытаться упростить его для этого особого случая. . Вероятность анализа Витерби до позиции k может быть упрощена до VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l). Вы можете связать l с максимальной длиной слова и найти, образуют ли l буквы слово с помощью хеш-поиска. Сложность этого не зависит от размера словаря и составляет O(<text length> <max l>). Извините, это не доказательство, а просто набросок, но он должен вас заинтересовать. Еще одна потенциальная оптимизация: если вы создаете словарь, вы можете проверить, является ли подстрока префиксом любого правильного слова. Поэтому, когда вы запрашиваете text[k-l:k] и получаете отрицательный ответ, вы уже знаете, что то же самое верно и для text[k-l:k+d] для любого d. Чтобы воспользоваться этим, вам придется значительно изменить рекурсию, поэтому я не уверен, что это можно полностью использовать (он может видеть комментарий).
Вот код в системе Mathematica, который я начал разрабатывать для недавнего гольфа.
Это нежадный рекурсивный алгоритм с минимальным сопоставлением. Это означает, что предложение "перо сильнее меча" (без пробелов) возвращает {"перо сильнее меча} :)
findAll[s_] :=
Module[{a = s, b = "", c, sy = "="},
While[
StringLength[a] != 0,
j = "";
While[(c = findFirst[a]) == {} && StringLength[a] != 0,
j = j <> StringTake[a, 1];
sy = "~";
a = StringDrop[a, 1];
];
b = b <> " " <> j ;
If[c != {},
b = b <> " " <> c[[1]];
a = StringDrop[a, StringLength[c[[1]]]];
];
];
Return[{StringTrim[StringReplace[b, " " -> " "]], sy}];
]
findFirst[s_] :=
If[s != "" && (c = DictionaryLookup[s]) == {},
findFirst[StringDrop[s, -1]], Return[c]];
Образец ввода
ss = {"twodreamstop",
"onebackstop",
"butterfingers",
"dependentrelationship",
"payperiodmatchcode",
"labordistributioncodedesc",
"benefitcalcrulecodedesc",
"psaddresstype",
"ageconrolnoticeperiod",
"month05",
"as_benefits",
"fname"}
Вывод
twodreamstop = two dreams top
onebackstop = one backstop
butterfingers = butterfingers
dependentrelationship = dependent relationship
payperiodmatchcode = pay period match code
labordistributioncodedesc ~ labor distribution coded es c
benefitcalcrulecodedesc ~ benefit c a lc rule coded es c
psaddresstype ~ p sad dress type
ageconrolnoticeperiod ~ age con rol notice period
month05 ~ month 05
as_benefits ~ as _ benefits
fname ~ f name
ХТН
Проверьте алгоритм исправления орфографии. Вот ссылка на статью об алгоритме, используемом в Google - http://www.norvig.com/spell-correct.html. Здесь вы найдете научная статья на эту тему от Google.
После выполнения рекурсивного разделения и поиска в словаре, чтобы повысить качество пар слов в вашей фразе, вам может быть интересно использовать взаимную информацию пар слов.
По сути, это то же самое, что пройти тренировочный набор и выяснить, что М.И. значения пар слов, которые говорят вам, что Альберт Симпсон менее вероятен, чем Альберт Эйнштейн :)
Вы можете попробовать поискать в Science Direct научные статьи по этой теме. Для получения основной информации о взаимной информации см. http://en.wikipedia.org/wiki/Mutual_information.
В прошлом году я участвовал в поиске по фразе в проекте поисковой системы, в котором я пытался проанализировать набор данных Википедии и ранжировать каждую пару слов. У меня есть код на C++, если вам интересно, могу поделиться им с вами, если вы найдете ему применение. Он анализирует викимедиа и для каждой пары слов находит взаимную информацию.
