н-граммы с использованием регулярных выражений

Question

Я работаю над программой расширенного и альтернативного общения (AAC). Моя текущая цель - хранить историю ввода / разговорного текста и искать общие фрагменты фраз или n-граммы слова. В настоящее время я использую реализацию, основанную на алгоритме сжатия lzw, как описано в CodeProject - N-грамм и алгоритм быстрого извлечения образца . Этот подход, хотя производство n-грамм не ведет себя должным образом.

Скажем, например, что я вхожу "через гору и через лес" несколько раз. Моим желаемым результатом была бы вся фраза «над горой и через лес». Используя мою текущую реализацию, фраза разбита на триграммы, и к каждой повторяющейся записи добавляется одно слово. Так что на первой записи я получаю "за гору". На второй записи "над горой" и т. Д.

Предположим, у нас есть следующий текст:

это тест
это еще один тест
это тоже тест
тест системы аварийного вещания прервал мою любимую песню

Моя цель состояла бы в том, чтобы, если бы после ввода «это тест системы аварийного вещания» я мог использовать его в регулярном выражении для возврата «это тест» и «тест системы аварийного вещания». Это то, что возможно с помощью регулярных выражений, или я иду по неправильному пути? Я ценю любую помощь.

Answer 1

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

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

блок-схема http://www.alsmatters.org/files/phraseextractor.png

Это анализирует стенограмму первых президентских дебатов (о16 500 слов) примерно за 30 секунд, что для моих целей довольно быстро.

Answer 2

В python вы можете использовать библиотеку fuzzywuzzy , чтобы сопоставить набор фраз с каноническим / нормализованным набором фраз через связанный список фраз или слов «синоним». Хитрость заключается в правильном сегментации ваших фраз (например, когда запятые разделяют фразы и когда они объединяют списки связанных слов в фразе?)

Вот структура python dict в RAM. Ваша структура данных в C или базе данных будет похожа:

phrase_dict = {
  'alternative phrase': 'canonical phrase',
  'alternative two': 'canonical phrase',
  'less common phrasing': 'different canonical phrase',
  }

from fuzzywuzzy.process import extractOne

phrase_dict[extractOne('unknown phrase', phrase_dict)[0]]

и это возвращает

'canonical phrase'

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

Answer 3

Из вашего варианта использования выясняется, что вам не нужны n-граммовые совпадения фиксированной длины, а самая длинная последовательность из n-граммовых совпадений. Только что увидел ответ на свой пост, что подтверждает;)