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

Question

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

Answer 1

Я бы загружал слова из словаря в структуру 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 willn '«правильное» слово).

Answer 2

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