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

Question

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

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

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

Однако проблемы, с которыми я сталкиваюсь:

• Учет составных ключевых слов, например, "ловит" может быть "ловит", "кошка" + "сыры"
• Разрешить буквальные термины - "то", "и", "один", "два", "три".
• Как предложить термины, которые не являются ключевыми словами. т.е. прибегнуть к чему-то похожему на системный словарь, когда ключевые слова или литералы не могут быть найдены
• Пропустить фрагменты фразы. Прямо сейчас это просто проходит. Но рассмотрим случай, когда фраза начинается с чего-то несопоставимого, но несколько символов позже содержат совпадения.

Я наиболее знаком с 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. Если вы не можете найти одно (обычно это только один слог слова), добавьте дополнительный слог и повторите поиск.

Пример:

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

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

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

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

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

C. Согласные звуки применяются

"Lah Jee Kahl Kon See Quinse"

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

"Law Gee Call Con Sea Quints"

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

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

выберите 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(), Наконец, свяжите два списка результатов, отсортировав их по положению и напечатав результат.

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

---

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