У меня есть алгоритм, который генерирует строки на основе списка входных слов. Как отделить только строки, которые звучат как английские слова? то есть. отбрасывайте RDLO, сохраняя LORD.
EDIT: Чтобы уточнить, им не нужно быть фактическими словами в словаре. Им просто нужно звучать как английский. Например, KEAL будет принята.
Вы можете построить марковскую цепочку огромного английского текста.
Затем вы можете кормить слова в цепочку марков и проверять, насколько высока вероятность того, что это слово является английским.
Смотрите здесь: http://en.wikipedia.org/wiki/Markov_chain
В нижней части страницы вы можете увидеть текстовый генератор марков. То, что вы хотите, точно противоположно этому.
В двух словах: сеть марков-цепочек для каждого символа, вероятности следующего следующего символа. Вы можете расширить эту идею до двух или трех символов, если у вас достаточно памяти.
Простой способ с байесовскими фильтрами (пример 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)]
Очень легко создавать английские звуковые слова, используя цепочку Маркова. Однако возвращение назад - это скорее вызов. Какая допустимая погрешность для результатов? Вы всегда можете иметь список общих буквенных пар, тройки и т.д. И оценивать их на основе этого.
Вы должны исследовать "объявляемые" генераторы паролей, поскольку они пытаются выполнить одну и ту же задачу.
Решение Perl было бы Crypt:: PassGen, которое вы можете обучать со словарем (чтобы вы могли обучать его различным языкам, если тебе нужно). Он просматривает словарь и собирает статистику по 1, 2 и 3-буквенным последовательностям, затем строит новые "слова" на основе относительных частот.
Вы могли бы подойти к этому путем токенизации строки-кандидата в bigrams - пары смежных букв - и проверку каждого биграма на таблицу английского языка bigram частот.
Любой из них потребует некоторой настройки порога (ов), второй метод больше, чем первый.
То же самое с триграммами будет более надежным, хотя, вероятно, это также приведет к несколько более строгим наборам "правильных" строк. Независимо от того, выиграет или нет, зависит от вашего приложения.
Таблицы Bigram и триграммы на основе существующих исследовательских корпусов могут быть доступны бесплатно или для покупки (я не нашел свободного доступа, но только сделал беглый google до сих пор), но вы можете рассчитать таблицу биграмм или триграмм от себя от любой крупный корпус английского текста. Просто прокрутите каждое слово в виде токена и подсчитайте каждый биграмм, вы можете обработать это как хэш с заданным bigram как ключ и счетчик с добавленным целым числом в качестве значения.
Английская морфология и английская фонетика (лихо!) меньше, чем изометрические, поэтому этот метод может генерировать строки, которые "смотрят" на английский, но представляют собой неприятные слова. Это еще один аргумент для триграмм, а не для биграмм: странность, создаваемая анализом звуков, которые используют несколько букв в последовательности для создания данной фонемы, будет уменьшена, если n-грамм охватывает весь звук. (Например, подумайте "плуг" или "цунами".)
Должны ли они быть настоящими английскими словами или просто строками, которые выглядят так, будто они могут быть английскими словами?
Если им просто нужно выглядеть как английские слова, вы можете сделать некоторый статистический анализ на некоторых реальных английских текстах и выяснить, какие комбинации букв происходят часто. Как только вы это сделали, вы можете выбросить строки, которые слишком маловероятны, хотя некоторые из них могут быть реальными словами.
Или вы могли бы просто использовать словарь и отклонять слова, которые в нем отсутствуют (с некоторыми скидками на множественные числа и другие варианты).
У меня возникло бы желание запустить алгоритм soundex над словарем английских слов и кэшировать результаты, а затем soundex вашу строку кандидата и сопоставить с кешем.
В зависимости от требований к производительности вы можете разработать алгоритм расстояния для звуковых кодов и принять строки в пределах определенного допуска.
Soundex очень прост в реализации - см. Wikipedia для описания алгоритма.
Пример реализации того, что вы хотите сделать, будет:
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.
EDIT. Ваш пример "KEAL" будет прекрасен, так как он имеет тот же код soundex (K400), что и "KEEL". Возможно, вам придется записывать отклоненные слова и вручную проверять их, если вы хотите получить представление о частоте отказа.
Metaphone и Двойной метафон аналогичные SOUNDEX, за исключением того, что они могут быть настроены больше на вашу цель, чем SOUNDEX. Они предназначены для "хэш-слов" на основе их фонетического "звука" и хорошо подходят для этого для английского языка (но не столько для других языков, либо для собственных имен).
Одна вещь, которую следует иметь в виду со всеми тремя алгоритмами, заключается в том, что они чрезвычайно чувствительны к первой букве вашего слова. Например, если вы пытаетесь выяснить, соответствует ли KEAL английское звучание, вы не найдете соответствия REAL, потому что исходные буквы отличаются. p >
Вы можете сравнить их со словарем (свободно доступным в Интернете), но это может быть дорогостоящим с точки зрения использования ЦП. Кроме этого, я не знаю ни о каком другом программном способе этого делать.
Это похоже на довольно сложную задачу! С головы до головы согласная фонема нуждается в гласной до или после нее. Определить, что такое фонема, будет довольно сложно! Вам, вероятно, придется вручную выписать список из них. Например, "TR" одобрен, но не "TD" и т.д.
Я бы, наверное, оценил каждое слово, используя алгоритм SOUNDEX, против базы данных английских слов. Если вы делаете это на SQL-сервере, довольно просто настроить базу данных, содержащую список большинства английских слов (используя свободно доступный словарь), а сервер MSSQL имеет SOUNDEX, реализованный как доступный алгоритм поиска.
Очевидно, вы можете реализовать это самостоятельно, если хотите, на любом языке, но это может быть довольно сложной задачей.
Таким образом, вы получите оценку того, насколько каждое слово будет звучать как существующее английское слово, если оно есть, и вы можете установить некоторые ограничения на то, насколько вы хотите принять результаты. Вероятно, вам стоит подумать о том, как объединить результаты для нескольких слов, и вы, вероятно, подберете пределы принятия на основе тестирования.
Я бы предложил посмотреть на фи-тест и индекс совпадения. http://www.threaded.com/cryptography2.htm
Я бы предложил несколько простых правил, и стандартные пары и триплеты были бы хорошими.
Например, английские звуковые слова имеют тенденцию следовать шаблону гласных-согласных-гласных, кроме некоторых дифтонгов и стандартных согласных пар (например, th, ie и ei, oo, tr). С такой системой вы должны вырезать почти все слова, которые не звучат так, как будто они могут быть английскими. При ближайшем рассмотрении вы обнаружите, что вы, вероятно, разделите много слов, которые также звучат как на английском, но вы можете приступить к добавлению правил, которые позволяют использовать более широкий диапазон слов и "тренировать" ваш алгоритм вручную.
Вы не удалите все ложные негативы (например, я не думаю, что вам удастся придумать правило, чтобы включить "ритм" без явного кодирования в этом ритме - это слово), но оно предоставит метод фильтрации.
Я также предполагаю, что вам нужны строки, которые могут быть английскими словами (они звучат разумно, когда произносится), а не строки, которые определенно являются словами с английским значением.