Сопоставьте аббревиатуры типа «ccd», «bbq», «phd» и т. Д. С большинством подобных строк из набора строк

Question

У меня есть список сокращений типа «ccd», «bbq», «phd» и т. Д.

для примера возьмем «BBQ», мы пытаемся сопоставить эту Сокращенно в список строк,

Barbeque Nation - Реальный ответ должен быть этот

барбекю Дым гриль

Пиво и печет Ворота

Как мы решаем, к какой строке принадлежат аббревиатуры. Я попытался использовать сопоставление строк с помощью алгоритма KMP и Longest Common Subsequence с добавленной настройкой добавления большего значения к строкам, которые были сопоставлены ранее.

Есть ли какая-либо структура данных, которая может помочь или любой алгоритм, который может иметь дело с такими случаями?

Спасибо!

Answer 1

Ahh, проблема с основным кодом. Моя специальность.

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

Модель дистанции редактирования будет определяться путем настройки на оценочную метрику. Существует хороший учебник по проверке орфографии в http://alias-i.com/lingpipe/demos/tutorial/querySpellChecker/read-me.html

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

Брек

Уточнение для последующего вопроса:

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

Таким образом, оценка словаря может заключаться в том, включена ли фраза в словаре или из него. Я бы начал с первого символьного совпадения со счетом -1 на слово в фразе и -1 для пропущенных функциональных слов во фразе типа 'и', -5 для пропуска буквы в аббревиатуре. Таким образом, «bbq», глядя на словарь, можно сопоставить с «Beer and Bakes Gates» со счетом -8 (-1 + -1 + -1 + -5)

«Начинание барбекю» потребует изменений что лучше. Таким образом, буква в одном слове получает десятки -5, а пропущенное слово - -6,5 (-5 + -. 5 + -. 5 + -5), что является лучшим показателем. Эти затраты на редактирование должны быть сбалансированы по сравнению с набором тренировок, который у вас есть, который должен быть несколько тысяч примеров, если вы хотите какой-либо общности.