Как определить, звучит ли случайная строка как английская?

Question

У меня есть алгоритм, который генерирует строки на основе списка входных слов. Как отделить только строки, которые звучат как английские слова? то есть. сбросьте RDLO , сохраняя LORD .

РЕДАКТИРОВАТЬ: Чтобы уточнить, они не должны быть реальными словами в словаре. Они просто должны звучать как английский. Например, KEAL будет принято.

Answer 1

Вы можете построить марковскую цепочку из огромного английского текста.

После этого вы можете ввести слова в цепочку марков и проверить, насколько высока вероятность того, что слово является английским.

Смотрите здесь: http://en.wikipedia.org/wiki/Markov_chain

Внизу страницы вы можете увидеть генератор текста markov. То, что вы хотите, это как раз наоборот.

В двух словах: цепочка марков хранит для каждого персонажа вероятности, за которыми последует следующий персонаж. Вы можете расширить эту идею до двух или трех символов, если у вас достаточно памяти.

Answer 2

Простой способ с байесовскими фильтрами (пример Python от http://sebsauvage.net/python/snyppets/#bayesian)

from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')

>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]

>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]

Answer 3

Вы можете подойти к этому, разбив строку кандидата на биграммы - пары смежных букв - и сравнив каждый биграмм с таблицей английских частот биграмм.

• Простой: если какой-либо биграмм достаточно низок в таблице частот (или вообще отсутствует), отклоните строку как неправдоподобную. (Строка содержит биграмму "QZ"? Отклонить!)
• Менее просто: вычислите общую правдоподобность всей строки в виде, скажем, произведения частот каждой биграммы на среднюю частоту действительной английской строки этой длины. Это позволило бы вам (а) принять строку с нечетным низкочастотным биграммом среди других высокочастотных биграмм и (б) отклонить строку с несколькими отдельными биграммами с низким, но не совсем ниже порогового значения ,

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

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

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

Английская морфология и английская фонетика (классно!) Меньше, чем изометрические, поэтому этот метод вполне может генерировать строки, которые «выглядят» по-английски, но вызывают неприятные неудобства. Это еще один аргумент в пользу триграмм, а не биграмм - странность, возникающая при анализе звуков, использующих несколько букв в последовательности для получения заданной фонемы, будет уменьшена, если n-грамм охватывает весь звук. (Например, подумайте «плуг» или «цунами».)

Answer 4

Довольно просто генерировать английские слова, используя цепочку Маркова. Однако идти назад - сложная задача. Каков допустимый предел погрешности для результатов? Вы всегда можете иметь список общих пар букв, троек и т. Д., И оценивать их на основе этого.

Answer 5

Вы должны исследовать «произносимые» генераторы паролей, поскольку они пытаются выполнить ту же задачу.

Решением Perl будет Crypt :: PassGen , которое вы можете обучить с помощью словаря (чтобы вы могли обучать его на разных языках, если вам нужно). Он просматривает словарь и собирает статистику по 1, 2 и 3-буквенным последовательностям, а затем строит новые «слова» на основе относительных частот.

Answer 6

Метафон и Двойной Метафон аналогичны SOUNDEX, за исключением того, что они могут быть настроены больше на вашу цель, чем SOUNDEX . Они предназначены для "хэширования" слов на основе их фонетического "звука" и хороши в этом для английского языка (но не для других языков и имен собственных).

При использовании всех трех алгоритмов следует помнить, что они чрезвычайно чувствительны к первой букве вашего слова. Например, если вы пытаетесь выяснить, звучит ли KEAL по-английски, вы не найдете совпадения с REAL , потому что начальные буквы разные.

Answer 7

У меня возникнет соблазн запустить алгоритм soundex для словаря английских слов и кешировать результаты, а затем выполнить soundex строку кандидата и сопоставить ее с кешем.

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

Soundex очень прост в реализации - описание алгоритма см. В Википедии .

Примером реализации того, что вы хотите сделать, будет:

def soundex(name, len=4):
    digits = '01230120022455012623010202'
    sndx = ''
    fc = ''

    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c
            d = digits[ord(c)-ord('A')]
            if not sndx or (d != sndx[-1]):
                sndx += d

    sndx = fc + sndx[1:]
    sndx = sndx.replace('0','')
    return (sndx + (len * '0'))[:len]

real_words = load_english_dictionary()
soundex_cache = [ soundex(word) for word in real_words ]

if soundex(candidate) in soundex_cache:
    print "keep"
else:
    print "discard"

Очевидно, вам потребуется предоставить реализацию read_english_dictionary.

РЕДАКТИРОВАТЬ : Ваш пример «KEAL» будет в порядке, поскольку он имеет тот же код soundex (K400), что и «KEEL». Возможно, вам придется регистрировать отклоненные слова и вручную проверять их, если вы хотите получить представление о частоте отказов.

Answer 8

Должны ли они быть настоящими английскими словами или просто строками, которые выглядят как английские слова?

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

Или вы можете просто использовать словарь и отклонять слова, которых в нем нет (с некоторыми допущениями для множественного числа и других вариантов).

Answer 9

Я бы посоветовал взглянуть на фи-тест и индекс совпадений. http://www.threaded.com/cryptography2.htm

Answer 10

Я бы предложил несколько простых правил, и стандартные пары и тройки были бы хороши.

Например, английские звучащие слова, как правило, следуют шаблону гласный-согласный-гласный, за исключением некоторых дифтонгов и стандартных пар согласных (например, th, т.е. ei, oo, tr). С такой системой вы должны удалить почти все слова, которые не похожи на английские. При ближайшем рассмотрении вы обнаружите, что, вероятно, вырежете много слов, которые звучат также как английский, но затем вы можете начать добавлять правила, которые допускают более широкий диапазон слов, и «тренировать» свой алгоритм вручную.

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

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