Алгоритм, использующий soundex () или metaphone () для создания фраз стиля Mad Gab

Question

Я пытаюсь создать алгоритм, который будет предлагать фразы типа Mad Gab .

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

• цикл по фразам (символ за символом)
  • , если найдено ключевое слово
    • сохранить ключевое слово и ответвление (рекурсия)
  • увеличение количества символов

Однако возникают следующие проблемы:

• Учетная запись длясоставные ключевые слова, например, «catches» могут быть «catches», «cat» + «cheeses»
• Разрешить буквальные термины - «the», «and», «one», «two», «three».
• Как предложить термины, которые не являются ключевыми словами.т. е. прибегнуть к чему-то похожему на системный словарь, когда ключевые слова или литералы не могут быть найдены.
• Пропуск сегментов фраз.Прямо сейчас это просто проходит.Но рассмотрим случай, когда фраза начинается с чего-то несопоставимого, но несколько символов позже содержат совпадения.

Я наиболее знаком с PHP и MySQL.Однако я открыт для другой технологии, если она обеспечивает лучшее решение.

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

Answer 1

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

http://www.ewsdonline.org/education/components/scrapbook/default.php?sectiondetailid=7584

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

http://www.tug.org/docs/liang/

Затем превратите каждый слог в фонетическое представление, используя то, что вы катите сами или метафон (). Вы можете использовать подобный сайт, который объясняет правила гласного звука. Это будут только обобщения. Вы будете обрабатывать гласные отдельно от согласных, если катите свои собственные. Метафон просто использует согласные, что хорошо, но не так круто, как если бы вы также учитывали гласные.

Гласные: http://www.eslgold.com/pronunciation/english_vowel_sounds.html Согласные буквы: http://usefulenglish.ru/phonetics/english-consonant-sounds

Тогда у вас есть словарь английских слов для вашего банка слов. Существует множество доступных словарей с открытым исходным кодом, которые можно вставить в таблицу MySQL.

Начните с первого слога и найдите в словаре случайное слово, которое соответствует тесту soundex. Если вы не можете найти одно (обычно это только один слог), добавьте дополнительный слог и повторите поиск.

* * Пример тысяча двадцать-один: * * 1 022

"Логическое следствие"

A. Слог раскол

"логическая последовательность"

B. Применены гласные звуки

"Lah Gee Cahl Con см Айва"

C. Согласные звуки

"lah jee kahl kon see quinse"

D. Тест Soundtext (один слог soundex - очевидно, слишком легко угадать, но он подтверждает концепцию)

"Law Gee Call Con Sea Quints"

Soundex strcmp возвращает число. Так что, если хотите, вы можете заранее получить значения soundex всего в вашем банке слов. Тогда вы можете быстро запустить strcmp.

Пример сравнения Soundex MySQL:

select strcmp (soundex ('lah'), soundex ('law'));

Я думаю, что использование soundex в MySQL проще для вас, чем тест soundex в PHP, если вы хотите получить случайный результат из большой базы данных, и вы уже захватили значение soundex в поле таблицы словаря.

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

Обновление:

Я не хотел подразумевать, что мое решение даст только один слог. Я использовал один слог в качестве примера, но если вы возьмете два слога вместе, вы получите многосложные совпадения. Фактически, вы могли бы просто начать с объединения всех слогов и запуска soundex в mysql. Если вы найдете ответ, отлично. Но тогда вы можете скатывать слоги, пока не получите максимально длинное совпадение. Тогда вы остаетесь с концом фразы и можете взять их вместе и провести матч. Я думаю, что это суть решения, представленного ниже, от другого участника, но я думаю, что вам нужно избегать объединения всех букв без пробелов. На английском вы потеряете информацию таким образом. Подумайте о фразе, начинающейся с "th" звука. Если вы смешиваете фразу вместе, вы теряете, какой "й" звук нужен. «Термен» (инструмент) имеет другой «й» звук, чем «Там, человек».

Answer 2

В отличие от решения Джонатана Барлоу , я рекомендую алгоритм O (n ² ), который дает вам свойства, которые вы ищете, в случайности, надежности и масштабируемой сложности. Сложность этого алгоритма может быть дополнительно улучшена в постоянном времени или с оптимизацией модальности поиска, но поскольку размер ваших входных фраз гарантированно будет небольшим, это не так уж и важно.

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

2. Рассматривайте слова во входной фразе как одну сжатую строку символов без какой-либо идентичности слова, отбрасывая пробел и все знаки препинания. После этого пройдитесь по пробелам для всех длин символов, начиная с длины один, до полной длины объединенной фразы минус один. Для каждой строки, полученной в результате этой прогулки, выполните поиск по хешу против OED. Когда встречается слово, присутствующее в словаре, добавьте его слово и позицию в конец списка в памяти.
   
   (Этот проход всегда будет занимать sum(n) время, что по определению 0.5n(n+1). Итак, O (n ² ) это так. Его пространственная сложность наихудшая O (n ² ), но на практике полностью связанный набор терминов крайне маловероятен .)

3. Теперь придет ваш ползунок сложности. Из созданного списка отрубите первые N% найденных терминов, где N - ваш уровень сложности. Принцип заключается в том, что слова меньшего размера легче лексически обрабатывать, в то время как более длинные слова труднее произносить и различать.

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

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

Это случайный алгоритм, который, как я считаю, обладает всеми желаемыми свойствами, но он все еще груб в моем уме.

---

* Дополнительный кредит: определите допустимые совпадения для вашей системы по символам или слогам. Это может обеспечить еще большую гамму принятых выходных фраз и значительно более высокий уровень сложности.