Нужен высокоэффективный алгоритм, чтобы проверить, содержит ли строка английскую речь

Question

У меня есть много строк. Все они содержат только символы. Символы и слова не разделяются пробелами друг от друга. Некоторые из персонажей образуют английские слова, а другие - просто баффлегаб. Строки не могут содержать целое предложение.

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

Я ищу высокопроизводительный алгоритм или метод, который проверяет, построены ли строки из английских слов или английской речи. Может быть, есть что-то, что дает мне шанс, что строка содержит английскую речь.

Знаете ли вы метод или алгоритм, который мне помогает? Помогает ли мне что-то вроде Sphinx ?

Answer 1

Если ваши строки достаточно длинные или ваш странный баффаб достаточно странный, буквенные частоты - возможно, также биграмные частоты, частоты триграмм и т. Д. - могут быть достаточными (вместо более общих N-граммов). Например, некоторые браузеры используют это для угадывания кодовой страницы.

Answer 2

Это называется проблемой сегментации .

Нет тривиального способа решить эту проблему. Исходя из того, что я могу предположить о вашем уровне знаний, я могу предложить вам построить trie из вашего словаря, и при первом же обнаружении возможного слова попробуйте предположить, что это слово.

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

Answer 3

Проверьте модель языка N-граммы.

См. http://en.wikipedia.org/wiki/N-gram

Answer 4

Это зависит от того, какую точность вы хотите, насколько она вам нужна, и какой текст вы обрабатываете.

Answer 5

Почему бы не сохранить свой список слов в Trie . Затем вы перебираете ввод, ища подходящие слова в Trie - это можно сделать очень эффективно. Если вы найдете его, перейдите к концу слова и продолжайте.

Answer 6

Сфинкс, вероятно, не поможет вам. Попробуйте алгоритм Рабина-Карпа . Это ужасно для стандартного поиска, но должно хорошо работать для этой конкретной проблемы. По сути, вы хотите иметь словарь английских слов и будете искать с ним. Слишком большие словари по-прежнему будут довольно медленными, но если вы используете небольшой словарь для общих слов и переключаетесь на большой только тогда, когда нажимаете общие слова, вы, вероятно, все равно не получите слишком много ложных отрицаний.