Проверка, содержит ли строка английское предложение

Вы можете ускорить поиск, используя Алгоритм Кнута-Морриса-Пратта (KMP).

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

Как насчет Bloom Filter?

Фильтр Блума, созданный Бертоном Ховардом Блумом в 1970 году, является
пространственно-эффективная структура вероятностных данных, используемая для проверки
является ли элемент членом набора. Ложные положительные совпадения
возможно, но ложных негативов нет; то есть запрос возвращает либо
«внутри набора (может быть неправильно)» или «определенно не в наборе». Элементы могут
быть добавленным в набор, но не удаленным (хотя это можно решить
с «счетным» фильтром). Чем больше элементов, которые добавляются к
установить, тем больше вероятность ложных срабатываний.

Подход может работать следующим образом: вы создаете набор слов, с которыми хотите проверять (это делается только один раз), а затем вы можете быстро выполнить проверку «in / not-in» для каждой подстроки. Если результат «не в», вы можете продолжить (фильтры Блума не дают ложных негативов). Если результат «в», то вы выполняете более сложную проверку для подтверждения (фильтры Блума могут давать ложные срабатывания).

Насколько я понимаю, некоторые средства проверки орфографии полагаются на фильтры Блума, чтобы быстро проверить, относится ли ваше последнее слово к словарю известных слов.

Теоретически, я думаю, вы должны быть в состоянии обучить марковскую модель и использовать ее, чтобы решить, является ли строка предложением или мусором. Есть еще один вопрос о том, как распознать слова, а не предложения: Как определить, звучит ли случайная строка как английская?

Единственная разница для обучения предложениям состоит в том, что ваши таблицы вероятностей будут немного больше. Однако, по моему опыту, современный настольный компьютер имеет более чем достаточно ОЗУ для обработки матриц Маркова, если вы не обучаетесь по всей Библиотеке Конгресса (что не нужно — даже 5 или более книг разных авторов должно быть достаточно для очень точной классификации) ,

Поскольку ваши предложения объединяются без четких границ слов, это немного сложно, но хорошая новость заключается в том, что марковская модель не заботится о словах, только о том, что следует за чем. Таким образом, вы можете заставить его игнорировать пробелы, сначала удалив все пробелы из ваших тренировочных данных. Если вы собираетесь использовать Алису в стране чудес в качестве учебного текста, первый абзац, возможно, будет выглядеть так:

alicewasbeginningtogetverytiredofsittingbyhersisteronthebankandofhavingnothingtodoonceortwiceshehadpeepedintothebookhersisterwasreadingbutithadnopicturesorconversationsinitandwhatistheuseofabookthoughtalicewithoutpicturesorconversation

Это выглядит странно, но что касается марковской модели, это тривиальное отличие от классической реализации.

Я вижу, что вы беспокоитесь о времени: обучение может занять несколько минут (при условии, что вы уже скомпилировали тексты «предложений» и «случайных зашифрованных строк» ​​золотого стандарта). Вам нужно только обучиться один раз, вы можете легко сохранить «обученную» модель на диск и повторно использовать ее для последующих запусков путем загрузки с диска, что может занять несколько секунд. Выполнение вызова строки потребует тривиально небольшого числа умножений с плавающей запятой, чтобы получить вероятность, поэтому после того, как вы закончите обучение, оно должно быть очень быстрым.

Этот код был изменен с Как разбить текст без пробелов на список слов?:

from math import log

words = open("english125k.txt").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)

def infer_spaces(s):
"""Uses dynamic programming to infer the location of spaces in a string
without spaces."""
# Find the best match for the i first characters, assuming cost has
# been built for the i-1 first characters.
# Returns a pair (match_cost, match_length).
def best_match(i):
candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)

# Build the cost array.
cost = [0]
for i in range(1,len(s)+1):
c,k = best_match(i)
cost.append(c)

# Backtrack to recover the minimal-cost string.
costsum = 0
i = len(s)
while i>0:
c,k = best_match(i)
assert c == cost[i]
costsum += c
i -= k

return costsum

С помощью тот же словарь этого ответа и тестирование ваших выходных данных

>>> infer_spaces("hithisisastringthatmustbechecked")
294.99768817854056

Хитрость здесь в том, чтобы выяснить, какое пороговое значение вы можете использовать, имея в виду, что использование меньших слов увеличивает стоимость (если алгоритм не может найти какое-либо пригодное для использования слово, он возвращает inf, так как это разделит все на однобуквенные слова).