Найдите слова в длинном потоке символов. Авто-токенизировать

Question

Как найти правильные слова в длинном потоке символов?

Ввод:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate"

Вывод Google:

"The revised report on syntactic theories sequential controlandstate"

(что близкоДостаточно, если учесть время, которое они произвели.

Как, по-вашему, это делает Google?Как бы вы увеличили точность?

Answer 1

Я бы попробовал рекурсивный алгоритм, подобный этому:

• Попробуйте вставить пробел в каждой позиции.Если левая часть является словом, то вернитесь к правой части.
• Подсчитайте количество действительных слов / общее количество слов во всех конечных выходных данных.Вероятно, ответом будет тот, который имеет наилучшее соотношение.

Например, если задать ему "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 в качестве ответа.1012 *

Answer 2

Попробуйте стохастическую регулярную грамматику (эквивалентную скрытым марковским моделям) со следующими правилами:

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 = .5? Это означает, что это вероятности в модели искусственного языка, где все слова одинаково вероятны, а все не-слова одинаково маловероятны.Конечно, вы могли бы сегментировать лучше, если бы вы не использовали это упрощение, но сложность алгоритма значительно снижается.Если вы посмотрите на отношение повторения в записи в википедии , вы можете попытаться упростить его для этого особого случая.Вероятность синтаксического анализа Витерби до позиции k можно упростить до VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l). Вы можете связать l с максимальной длиной слова и определить, образуют ли все буквы слово с помощью поиска по хешу.Сложность этого не зависит от размера словаря и составляет O(<text length> <max l>).Извините, это не доказательство, просто набросок, но вы должны начать.Еще одна потенциальная оптимизация: если вы создаете три словаря, вы можете проверить, является ли подстрока префиксом любого правильного слова.Поэтому, когда вы запрашиваете текст [kl: k] и получаете отрицательный ответ, вы уже знаете, что то же самое верно для текста [kl: k + d] для любого d.Чтобы воспользоваться этим преимуществом, вам необходимо значительно изменить рекурсию, поэтому я не уверен, что это можно использовать в полной мере (см. Комментарий).

Answer 3

Вот код в 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

НТН

Answer 4

После выполнения рекурсивного разбиения и поиска в словаре для повышения качества пар слов в вашей фразе вас может заинтересовать использование Взаимной информации о парах слов.

Это, по сути, происходит через тренировочный набор и обнаруживает М.И. значения пар слов, которые говорят вам, что Альберт Симпсон менее вероятно, чем Альберт Эйнштейн:)

Вы можете попробовать поискать в Science Direct научные статьи по этой теме. Для получения базовой информации о взаимной информации см. http://en.wikipedia.org/wiki/Mutual_information

В прошлом году я участвовал в поисковой фразе проекта поисковой системы, в котором я пытался проанализировать набор данных Википедии и оценить каждую пару слов. У меня есть код на C ++, если вы можете поделиться им с вами, если вы можете найти его использование. Он анализирует Викимедиа, и для каждого слова пара находит взаимную информацию.

Answer 5

Проверьте алгоритм исправления орфографии. Вот ссылка на статью об алгоритме, используемом в Google - http://www.norvig.com/spell-correct.html. Здесь вы найдете научную статью по этой теме от Google