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

StackOverflow https://stackoverflow.com/questions/92006

  •  01-07-2019
  •  | 
  •  

Вопрос

У меня есть алгоритм, который генерирует строки на основе списка входных слов.Как мне отделить только те строки, которые звучат как английские слова?т.е.выбросить РДЛО сохраняя при этом ГОСПОДИ.

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

Это было полезно?

Решение

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

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

Смотрите здесь: 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)]

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

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

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

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

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

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

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

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

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

Метафона и Двойной Метафон похожи на 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".Возможно, вам потребуется зарегистрировать отклоненные слова и вручную проверить их, если вы хотите получить представление о частоте отказов.

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

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

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

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

Это звучит как довольно сложная задача!На мой взгляд, согласная фонема нуждается в гласной либо перед, либо после нее.Однако определить, что такое фонема, будет довольно сложно!Вероятно, вам придется вручную составить их список.Например, "TR" - это нормально, но не "TD" и т.д.

Я бы, вероятно, оценил каждое слово, используя алгоритм SOUNDEX, по базе данных английских слов.Если вы делаете это на SQL-сервере, должно быть довольно легко настроить базу данных, содержащую список большинства английских слов (используя свободно доступный словарь), а на сервере MSSQL SOUNDEX реализован как доступный алгоритм поиска.

Очевидно, что вы можете реализовать это самостоятельно, если хотите, на любом языке, но это может оказаться непростой задачей.

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top