Подсчет английских слов в случайной строке

Question

Предположим, у меня есть случайная сгенерированная строка s=t&^%JHGgfdteam*&HGEdfg, каков наилучший способ подсчета количества английских слов в этой строке? (Английские слова, определенные в некоторых словарных файлах). Очевидно, что грубая сила - это не очень хорошая идея ... будет ли суффикс-три? Двоичный поиск? Обратите внимание, что в случае s есть два слова: «чай» и «команда». Любые идеи? С уважением

Answer 1

Я бы загрузил словарные слова в структуре Trie, затем прочитал строку слева направо и проверил, находятся ли подстроки в trie. Если они есть и есть дети, продолжайте идти. Если они оказались листом или действительным словом, добавьте к счету вхождения.

В псевдокоде:

Trie dict = ... // load dictionary 
Dictionary occurences = {} 

for i in length(string): 
    j = i + 1 
    # think of partial as string.Substring(i, j); 
    while dict.hasChildren(partial): 
     j++ 
     if isWord(partial): 
      dict[partial]++ 

Таким образом, вы будете гарантировать, что это не пропустите матч в то время как все еще ищет все возможности.

Вы можете ограничить минимальную длину правильных слов, изменяя то, что j инициализируется или отклоняя короткие слова в методе isWord() (так a не будет «действительным» слово).

Answer 2

Aho-Corasick string matching algorithm строит согласованную структуру во времени, линейную по размеру словаря, и соответствует шаблонам в момент времени, линейный по размеру вводимого текста + количество найденных совпадений.