Comments 13
Хорошо получилось! Как-то тоже пришлось дорабатывать алгоритм Левенштейна под свои нужды. Причина была такая же - алгоритм хорошо сравнивает два отдельных слова, а вот два предложения - уже не очень. Кратко о том, к чему я пришёл в тот раз:
в сравниваемых текстах идентичные слова исключались из сравнения
оставшиеся слова перед сравнением сортировались по алфавиту, так как порядок слов не был важен в моей предметной области
полученное расстояние нормировалось на исходную длину строк, включая исключённые на первом этапе слова
Что интересно, в комментариях отметился ещё один разработчик, который в той же предметной области решал похожую проблему и тоже использовал расстояние Левенштейна.
Добрый день! Благодарим!
Было бы интересно узнать, какую задачу анализа текстов Вы решали? Предложения уже были выделены или извлекались динамически?
В некоторых задачах мы ищем n-граммы (n – от 2-х до 5-ти) в строке с удаленными пробелами. Наш опыт показывает, что без штрафов f(G(V), W) здесь не обойтись.
Проблема была такая: оптимизировать размещение товаров на складе.
Один из критериев оптимальности - размещение в одной ячейке товаров с непохожими названиями. В противном случае встречается такая ситуация:
сборщику товара приказали собрать 14 упаковок 5-мл. шприцов по 10 шт. от производителя ООО "АБВГД".
он подходит к нужной ячейке, а там десятки разновидностей в общем-то одинаковых шприцов: есть 5 мл по 10 шт, но другой производитель, есть тот же производитель, но 10 мл. по 5 штук и т. п.
сборщик путается, берёт не тот товар, в итоге это оборачивалось штрафом для него и недовольством для клиента
если в ячейке лежат непохожие товары: один вид перчаток, один вид витаминок, один вид противовирусного и лишь один вид шприцов, то сборщику ошибиться гораздо тяжелее.
Я как-то давно занимался совоставлением распознанного текста с текстом из pdf. Из pdf текст иногда достаётся странно. Например, могут потеряться все пробелы, или жирный шрифт моделируется тем, что буква удваивается-утраивается, бывают проблемы с "кракозябрами" и ещё всякое разное. Помню, что приходилось дополнительно настраивать штрафы для удаления/вставки (у вас они = 1). Например, удаление пробельных символов штрафовать слабее. Потом нужно восстановить набор операций, соответствующие минимальному расстоянию. Таких наборов может быть несколько и выбирался "наилучший". Вот здесь и были самые большие проблемы, так как наборов операций с одним и тем же штрафом могло быть много и не все они были хорошими по другим соображениям.
Приветствуем! Спасибо за ваш комментарий!
Ваш опыт сопоставления слов распознанного текста с текстом из pdf очень интересен! Было бы интересным почитать или провести эксперименты, связанные с тем, что слова модель тоже могут содержать ошибки.
У нас цена удаления/вставки равна 1, поскольку удаление/вставка символа в распознанном слове чаще проявляется из-за ошибок распознавания нескольких подряд идущих символов. То есть не было необходимости особым образом реагировать на такие ошибки.
В статье не рассмотрены ошибки поиска слов: когда слово при распознавании разбито на части (лишние пробелы) или когда объединились несколько слов (потеря пробела). Кстати, такие случаи возможны не только из-за распознавания, иногда в деловых документах между словом статического текста и словом заполнения в самом деле отсутствует пробел.
Вопрос неспециалиста в данной теме, но интересующегося. В определении оригинального расстояния Левенштейта i и j - это длины слов V и W?
И еще вопрос ближе к математике. Если задан набор символов для всех возможных исследуемых слов, то каждое слово можно задать матрицей, в которой почти все элементы нули, а единицы стоят на местах, соответствующих номеру символа в базовом наборе и месту символа в слове. Скорее всего, это стандартный подход. Но в этом случае "близость" слов можно оценить матричными методами, в т.ч. с использованием сингулярного разложения. Существует ли такой метод?
Добрый день! Благодарим за интерес к материалу.
1. Длины слов V и W - это |V| и |W|, соответственно. i и j - это индексы от 0 до длины соответствующей строки.
2. Другим способом вычисления расстояния между словами является применение расстояния мультимножества. Если задан набор кодов всех возможных символов (алфавит), то любое слово можно представить в виде мультимножества, носителем которого является алфавит. Слово в виде мультимножества представляет собой не матрицу, а вектор. В этом векторе значение 0 в некоторой компоненте означает отсутствие соответствующего символа в слове. А ненулевая компонента – сколько раз символ присутствующих в слове. Расстояние (метрика) мультимножества для двух слов вычисляется как сумма абсолютных значений разностей значений компонент двух описанных векторов. Действительно, Это - стандартный подход к сравнению слов. Однако при применении метрики мультимножества оказываются идентичными слова с перестановками символов. Например, по этой метрики идентичны все слова: XYZ, XZY, YXZ, YZX, ZXY, ZYX.
Если Вы можете написать формулы для оценки близости слов с помощью сингулярного разложения матриц, мы можем обсудить эту идею подробно. Нам такой подход неизвестен.
Спасибо за ответ. Я немного погуглил, но пока алгоритмов основанных на представлении слов в виде матриц KxN, где K - количество букв в слове, а N - количество символов в базовом наборе символов (алфавите) не увидел. Конечно, кто-то это использует, потому что идея ну совсем естественная. При самом простом подходе матрица содержит K единиц, остальные нули, поэтому проблемы с обработкой не должно возникнуть. Если сравнивать слова одной длины, то метрика строится очень просто, так как при умножении "слова" на самое себя получается единичная матрица, и чем больше несовпадений букв в паре сравниваемых, тем больше нулей на диагонали результата. Белее-менее понятно, как поступить с опечатками или "похожими" буквами типа И и Й или I, l, 1. Непростой кажется процедура сравнения слов разной длины, но если с этим внятно разобраться, то получается очень простой переход к однокоренным словам, что, в свою очередь, тоже является популярной задачей.
Спасибо за ответ. Мы прокомментируем некоторые мысли:
1) Покритикуем тезис «идея ну совсем естественная». Для слов одной длины естественно применять что-то вроде метрики Хэмминга. Для сравнения двух слов длины K потребуется ровно K операций сравнения (вызовов функции substCost). В реализации Вашей идеи потребуется: преобразование каждого слова в матрицу и операции над матрицами (умножение матриц). Это будет существенно медленнее, чем с применением метрики Хэмминга, то есть для программиста не совсем естественно.
2) «Более-менее понятно, как поступить с опечатками или "похожими" буквами типа И и Й или I, l, 1.» - было бы интересно узнать, что Вы предлагаете для множественных опечаток (нескольких подряд идущих опечаток)?
3) «Непростой кажется процедура сравнения слов разной длины» - без такой процедуры отождествлять слова вряд ли получится. Если у Вас есть подробные соображения, было бы интересно их прочесть.
Спасибо Вам за реакцию. Мои соображения по пунктам:
1) В таком матричном представлении почти все элементы - нули, и в простейшем случае в каждой строке всего одна единица (или true). Такие матрицы нет смысла хранить и обрабатывать "целиком". По сути это тот же самый вектор длины К (длина слова), в каждой компоненте которого хранится индекс, соответствующий месту буквы в алфавите. Чтобы посчитать расстояние Хемминга даже нечего умножать, все делается как обычно, покомпонентным сравнением. Зато можно продвинуться значительно дальше.
2) Можно поработать с опечатками и чередующимися гласными в однокоренных словах (типа раст-рост). Если есть "опасность" перепутать буквы И и Й, то в соответствующей строке матрицы ставятся два ненулевых элемента (веса 1/2 или sqrt(2)/2) на соответствующих местах, например на 10 для И и 11 для Й. Если можно перепутать три значения (I (заглавное i), l (строчное L) или 1), то ненулевые значения (веса) появляются в трех местах (по 1/3 или sqrt(3)/3). Тут уже в каждой компоненте вектора длины К будет храниться список или словарь с индексами и весами. Матрица, по большому счету, все равно остается вектором.
3) После некоторых раздумий мне кажется, что проблем в сравнении слов различной длины нет. Скорее наоборот, очень интересно получается. Если в словах есть совпадающие участки (например, общий корень), то в матрице, получающейся в результате умножения, будут "цепочки" ненулевых элементов (возможно, единиц, это зависит от выбранных весов) вдоль главной диагонали. Например, при сравнении слов "растение" и "вырастайка" будет цепочка из 4-х единиц, соответствующих общему корню "раст" и еще 2 "отдельно стоящих" единицы из-за повторения буквы "а".
Наверное, придумаю что-нибудь на Питоне, в тему начинает затягивать.
Каково расстояние между «Будапештом» и «Бухарестом» или об отождествлении слов с помощью расстояния Левенштейна