Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2      [все]
 Нормализация строк  [new]
Mixon
Member

Откуда:
Сообщений: 358
День добрый!
Подскажите как определить что
"Яблочное пюре" и "Пюре яблочное" в принципе одно и тоже, данные как пример, слова могут видо изменяться типа "Пюре из яблок".

Заранее спасибо за советы!
12 окт 21, 15:12    [22382679]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Никанор Кузьмич
Member

Откуда: Село Малые Кулики
Сообщений: 696
Встречный вопрос: "человек разумный" и "разумный человек" - это в принципе одно и то же или нет?
12 окт 21, 15:14    [22382682]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
В данном случае можно разбить на слова и отсортировать по алфавиту, но это не всегда работает, есть исключения когда порядок слов играет роль.
Сходу пример не придумаю, близкое: "копчено-вареный" и "варено-копченый" это два разных способа приготовления.
12 окт 21, 16:04    [22382713]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
По хорошему надо какую-то классификацию слов вводить. Например в данном случае слово "пюре" это форма выпуска, "яблочное" это вкус. Для нормализации достаточно например идентифицировать форму выпуска и убрать в сторону как признак товара. Тогда сначала отдельно сравниваем форму, а если совпала, то остальное. Но в остальном тоже могут быть подставы типа "Пюре яблочное с корицей".

Сообщение было отредактировано: 12 окт 21, 15:58
12 окт 21, 16:09    [22382716]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
WebSharper
Member

Откуда:
Сообщений: 573
Наверное, как-то так
12 окт 21, 17:09    [22382753]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
WebSharper
Наверное, как-то так

Нет, распознавание речи тут мало поможет. Оно заточено на разговорный язык.
Наименования товаров далеки от обычного разговорного, это не связное предложение, а набор характеристик, причем многие написаны сокращенно.
12 окт 21, 20:00    [22382819]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
exp98
Member

Откуда:
Сообщений: 3192
Х-ха! Семантику по грамматике ))
Меня однажды попробавали нагнуть автоматизацией поиска в инете. По названию товара неизвестно где выявить его цену))
12 окт 21, 21:03    [22382847]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
Mixon
День добрый!
Подскажите как определить что
"Яблочное пюре" и "Пюре яблочное" в принципе одно и тоже, данные как пример, слова могут видо изменяться типа "Пюре из яблок".

Заранее спасибо за советы!

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

В противном случае - она просто переходит в область ЗПТ или дискуссий ВопросОтвет.

Давайте перечислим алгоритмы нормализации строк Русского языка.
Я делаю упор на Русский язык потому-то нормализация другого языка
будет скорее всего совсем другим алгоритмом. Как "сумма прописью".

Потом поищем готовые реализации этих алгоритмов.

И потом поищем справочники слов или базы данных если таковые нужны.
13 окт 21, 16:06    [22383209]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
x1ca4064
Member

Откуда:
Сообщений: 1356
Mixon
Подскажите как определить что
"Яблочное пюре" и "Пюре яблочное" в принципе одно и тоже, данные как пример, слова могут видо изменяться типа "Пюре из яблок".

Заранее спасибо за советы!

Необходимо ввести расстояние между названиями: когда решал подобную задачу для наименований алкоголя, использовал расстояние Левенштейна (РЛ) и "ручной подбор", т.е. оператор для каждого наименования видел отсортированный по РЛ список кандидатов, оттуда и выбирал, так строился справочник. Сейчас можно попробовать вместо РЛ использовать какой-нибудь Word2Vec и считать расстояние между векторами.
Конкретная реализация, думаю, должна зависеть от предметной области: сколь автоматическим/точным должен быть подбор, сколько и каких строк нужно сравнивать (список названий или произвольные тексты).

Сообщение было отредактировано: 13 окт 21, 16:45
13 окт 21, 16:56    [22383237]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ы2
Member

Откуда:
Сообщений: 251
Mixon, можно попробовать использовать триграммное сходство. Например, его реализация в PostgreSQL считает, что «яблочное пюре» и «пюре яблочное» не различаются вовсе, а сходство любой из этих строк с «пюре из яблок» около 47%.
13 окт 21, 17:59    [22383279]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
Ы2
Mixon, можно попробовать использовать триграммное сходство. Например, его реализация в PostgreSQL считает, что «яблочное пюре» и «пюре яблочное» не различаются вовсе, а сходство любой из этих строк с «пюре из яблок» около 47%.

А "яблочная репа" будет ближе к "яблочному пюре" нежели чем "пюре из яблок".

Вот такой метафизический парадокс.
13 окт 21, 18:36    [22383296]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
mayton
Давайте перечислим алгоритмы нормализации строк Русского языка.

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

Штрихкод легко решает все проблемы на 99%
13 окт 21, 21:40    [22383357]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
Ы2
Mixon, можно попробовать использовать триграммное сходство. Например, его реализация в PostgreSQL считает, что «яблочное пюре» и «пюре яблочное» не различаются вовсе, а сходство любой из этих строк с «пюре из яблок» около 47%.

Жёлтый и белый тоже очень похожи по написанию
13 окт 21, 21:51    [22383362]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
Штрихкод - это не тема топика вроде как.
14 окт 21, 12:51    [22383586]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
exp98
Member

Откуда:
Сообщений: 3192
Точно также поступил, когда нормализовывал улицы, писанные вразнобой.
x1ca4064
Необходимо ввести расстояние между названиями ... "ручной подбор" ...
должна зависеть от предметной области
Ещё использовал модель ошибок в написании. Т.к. из подвохов могут быть латинские вместо русских и наоборот, очепятки-перестановки, регистр и прочее. МО - почти единственное, могущее быть для универсальной нормализации.
Ещё подвох - омонимы и какая-никакая контекстная зависимость.
14 окт 21, 15:18    [22383715]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
mayton
Штрихкод - это не тема топика вроде как.

Я так понимаю ТС хочет находить одинаковые товары по разному написанные. Большинство товаров нынче имеют штрихкод.
14 окт 21, 15:26    [22383723]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ы2
Member

Откуда:
Сообщений: 251
Dima T
Ы2
Mixon, можно попробовать использовать триграммное сходство. Например, его реализация в PostgreSQL считает, что «яблочное пюре» и «пюре яблочное» не различаются вовсе, а сходство любой из этих строк с «пюре из яблок» около 47%.

Жёлтый и белый тоже очень похожи по написанию

Это вам только кажется. У них триграммное сходство 8,3%.
14 окт 21, 16:17    [22383767]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
Dima T
mayton
Штрихкод - это не тема топика вроде как.

Я так понимаю ТС хочет находить одинаковые товары по разному написанные. Большинство товаров нынче имеют штрихкод.

Вернемся к яблокам.

Для данного частного случая:

Яблочное пюре - пюре из яблок


Я-бы предложил следующее.

Триграммный поиск - не вариант т.к. тут не опечатка а морфологическое преобразование.
Нам нужно все слова и выражения свести к единой основе.

ЯБЛОКО ПЮРЕ


и обеспечить правильный порядок. Можно задать ранг слов или положить их в SortedSet.

По триграммам. Про близость "пюре" и репа я уже писал. Надо практически посмотреть и взять хотя-бы штук 100-200
реальных названий и прогнать их по тесту.

Короче сложность решения задачи сильно зависит от качества самих исходных данных. Триграммы и биграммы и прочие N-граммы
это - слишком простой подход. Он может даже и не на текст ориентирован на например на генетику (биологию)
и он может хорошо работать в одних случаях, а в случаях с мофологией и лемматизацией он может просто
давать очень плохие результаты.
14 окт 21, 17:44    [22383813]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
Ы2
Dima T
пропущено...

Жёлтый и белый тоже очень похожи по написанию

Это вам только кажется. У них триграммное сходство 8,3%.

Триграмное да, а левенштейн очень близок, выделил совпадающие буквы: ЖЕЛТЫЙ БЕЛЫЙ
14 окт 21, 21:51    [22383952]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ы2
Member

Откуда:
Сообщений: 251
mayton, близость «пюре» и «репа» — еще более мнимая, чем «желтый» и «белый»: триграммное сходство 0%, РЛ = 4 и равно длине слова.

«яблочная репа» дальше от «яблочное пюре» (27%), чем «пюре из яблок» (47%).

Вы ошибочно полагаете, что триграммное сходство — для поиска опечаток. Оно для поиска строк, совпадающих по большей части. Для опечаток — расстояние Левенштейна.

Поэтому, на мой взгляд, самое простое решение — сформировать по триграммам список кандидатов на отождествление и отдать оператору, пусть решает вручную.
14 окт 21, 22:48    [22383982]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1769
Если решать в лоб, то можно
1) составить словарь нормализованных строк
2) посчитать для этого словаря N-граммы
3) затем для входных строк применять какую-нибудь очистку, если требуется (с помощью регулярных выражений и т.п.)
4) вычислять для них такие же N-граммы
5) сравнивать их с N-граммами из словаря, можно просто перемножением векторов, можно с помощью TF-IDF
6) установить порог, выше которого считаем, что строки похожи, например, 0.8 (подбирается экспериментально путём подсчета ошибок при разных значениях)
7) если в словаре найдено похожее слово, с мерой похожести выше порога, то считаем его нормализованным представлением строки
8) скорее всего, алгоритм не будет давать 100% результат, смотрим что получается и дальше накручиваем ещё какие-нибудь эвристики

Я, например, использовал такой подход для нормализации адресов. В качестве словаря использовал ФИАС. Использовал биграммы, а не триграммы (тут можно поэкспериментировать). Использовал кучу регулярок для разбиения адреса на части (регион, город, улица, дом и т.д.) и сравнивал каждую часть адреса отдельно, потому что очень много похожих слов типа Свердловская область, улица Свердлова, проспект Свердлова и т.п. Если сравнивать регионы, улицы и т.п. отдельно, то это существенно улучшает алгоритм. Плюс для ускорения и оптимизации можно сначала определить регион, а потом искать совпадения уже внутри него.

Соответственно вы тоже можете попробовать использовать эти штуки (если это применимо):
1) Разбить строку на части, сравнивать слова отдельно
2) Каким-то образом отнести строку к одной из подкатегорий и сравнивать только со строками этой категории
3) Использовать регулярки для предварительной очистки или разбиения строк

Ещё можно посмотреть https://yandex.ru/dev/mystem/ может пригодится.

И конечно же можно посмотреть https://rusvectores.org/ Они как и N-граммы позволяют превращать слова в векторы, но(!) таким образом, что близкие по смыслу слова имеют близкие векторы. Это позволяет делать вещи типа семантических калькуляторов, поиска аналогий, поиска похожих вещей и т.п.
15 окт 21, 04:59    [22384028]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
Погуглил немного, вот реальные наименования из предложений в инете:
ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100,0
ФрутоНяня Пюре яблоко натур 100г N 1
Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г


А есть еще такие:
Пюре ФрутоНяня Груша с 4 месяцев 100.000 г
Фрутоняня пюре 100 г груша/яблоко

Можно еще поискать
15 окт 21, 07:32    [22384039]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ы2
Member

Откуда:
Сообщений: 251
Dima T
Погуглил немного, вот реальные наименования из предложений в инете:
ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100,0
ФрутоНяня Пюре яблоко натур 100г N 1
Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г


А есть еще такие:
Пюре ФрутоНяня Груша с 4 месяцев 100.000 г
Фрутоняня пюре 100 г груша/яблоко

Можно еще поискать


with a (t) as (
	values ('ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100,0'),
		('ФрутоНяня Пюре яблоко натур 100г N 1'),
		('Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г'),
		('Пюре ФрутоНяня Груша с 4 месяцев 100.000 г'),
		('Фрутоняня пюре 100 г груша/яблоко')
)
select
	a.t,
	b.t,
	similarity(a.t, b.t)
from a, a as b
where a.t <> b.t
order by similarity desc;


вариант 1вариант 2сходство
Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 гПюре ФрутоНяня Груша с 4 месяцев 100.000 г0.75
Пюре ФрутоНяня Груша с 4 месяцев 100.000 гПюре ФрутоНяня Яблоко с 4 месяцев 100.000 г0.75
Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 гФрутоняня пюре 100 г груша/яблоко0.5833333
Фрутоняня пюре 100 г груша/яблокоПюре ФрутоНяня Яблоко с 4 месяцев 100.000 г0.5833333
Фрутоняня пюре 100 г груша/яблокоФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.00.575
ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0Фрутоняня пюре 100 г груша/яблоко0.575
Фрутоняня пюре 100 г груша/яблокоФрутоНяня Пюре яблоко натур 100г N 10.5681818
ФрутоНяня Пюре яблоко натур 100г N 1Фрутоняня пюре 100 г груша/яблоко0.5681818
Фрутоняня пюре 100 г груша/яблокоПюре ФрутоНяня Груша с 4 месяцев 100.000 г0.5416667
Пюре ФрутоНяня Груша с 4 месяцев 100.000 гФрутоняня пюре 100 г груша/яблоко0.5416667
ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0ФрутоНяня Пюре яблоко натур 100г N 10.5
ФрутоНяня Пюре яблоко натур 100г N 1ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.00.5
Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 гФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.00.48979592
ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г0.48979592
ФрутоНяня Пюре яблоко натур 100г N 1Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г0.46296296
Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 гФрутоНяня Пюре яблоко натур 100г N 10.46296296
Пюре ФрутоНяня Груша с 4 месяцев 100.000 гФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.00.39215687
ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0Пюре ФрутоНяня Груша с 4 месяцев 100.000 г0.39215687
ФрутоНяня Пюре яблоко натур 100г N 1Пюре ФрутоНяня Груша с 4 месяцев 100.000 г0.30508474
Пюре ФрутоНяня Груша с 4 месяцев 100.000 гФрутоНяня Пюре яблоко натур 100г N 10.30508474


Не идеально, конечно, но можно начинать что-то городить вокруг этого.
15 окт 21, 09:41    [22384073]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1769
Ы2
но можно начинать что-то городить вокруг этого
Например, с помощью регулярок отделить массу и возраст. Ещё можно составить отдельные словари для типов продукции (пюре), для сырья (яблоко, груша), для брендов (ФрутоНяня), сначала можно сопоставлять отдельные слова, каждое из них приводить к нормализованному виду (как в словаре), а затем уже сопоставлять всю строку, в которой каждое отдельное слово уже нормализовано. Не знаю даст это что-то или нет, но в таких задачах первый шаг делается легко, но потом разобраться со всякими крайними случаями - целая история.

Тут ещё непонятен вопрос. Нужно сравнивать все строки со всеми, тогда это задача кластеризации. Либо всё-таки есть словарь правильных, нормализованных строк, и нужно сравнивать новые строки со словарем.
15 окт 21, 10:02    [22384083]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
Ы2
where a.t <> b.t

Чтобы не двоилось лучше так
where a.t > b.t


Ы2
Не идеально, конечно, но можно начинать что-то городить вокруг этого.

ИМХО, как выше написали, начинать надо с выделения характеристик: брэнд, тип, вкус, вес и т.д. а дальше нераспознанное можно этим способом досравнивать.
15 окт 21, 10:29    [22384092]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
Вот этот суффикс типа

4 месяцев 100.000 г


тоже может сильно изменить формулу дистанции. Могут быть ложные срабатывания для других товаров.

Кстати этот similarity(..) какой алгоритм использует?
15 окт 21, 10:31    [22384094]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
exp98
Member

Откуда:
Сообщений: 3192
Dima T
Погуглил немного, вот реальные наименования из предложений в инете:
А есть еще такие:
Можно еще поискать
Dima , Ы2, отставить спам, отставить брутальную рекламу брэнда ... ))
15 окт 21, 12:31    [22384175]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Dima T
Member

Откуда:
Сообщений: 16063
exp98
Dima T
Погуглил немного, вот реальные наименования из предложений в инете:
А есть еще такие:
Можно еще поискать
Dima , Ы2, отставить спам, отставить брутальную рекламу брэнда ... ))

Что первое гугл выдал, то и скопипастил. Хорошо в рекламу вкладываются видать. Так что наше упоминание им продажи не увеличит.
А в остальном этот бренд гадость редкостная, когда дети маленькие были жена говорила не брать его ни при каком раскладе
15 окт 21, 12:45    [22384187]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
exp98
Member

Откуда:
Сообщений: 3192
mayton
Могут быть ложные срабатывания для других товаров.
А как определить близость 1 кг помидоров и 1 кг томатов?
У нас в Перекрёстки с недавних лет помидоров не стало, их постепенно вытеснили томаты. А так хочется помидорчиков!
А что в других регионах?
15 окт 21, 13:02    [22384196]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
exp98
Member

Откуда:
Сообщений: 3192
mayton
Вот этот суффикс типа
4 месяцев 100.000 г
Наверняка это другие поля из БД, тогда на них метрика не распространится. А "чеснок фасованный" и в развес ??
Не знаю новейших практик. М.б. подобное уже зашивают в классификациютоварных групп?
Например одежда изначально классифицировалась матрично: цвето-размер.

Прикол по случаю
+
В маге на стенке есть считыватели штрих-кода, чтоб мы сами цену узнавали. Иногда они зависают. Раз я взял и перезапустил девайс, а там загрузился маленький Виндовс. Не помню, то ли через "Пуск" загрузил прогу, или не удалось...


Сообщение было отредактировано: 15 окт 21, 13:04
15 окт 21, 13:07    [22384198]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ares_ekb
Member

Откуда: Екатеринбург
Сообщений: 1769
exp98,

Можно тут найти похожие слова для "помидор" https://rusvectores.org/
автор
огурец 0.775
морковь 0.726
овощ 0.711
баклажан 0.706
капуста 0.704
арбуз 0.701
салат 0.690
чеснок 0.687
томат 0.684
фасоль 0.670

Помидор больше похож на огурец, чем на томат. На этот случай наверное нужен свой словарь синонимов
15 окт 21, 13:14    [22384204]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ы2
Member

Откуда:
Сообщений: 251
mayton
Вот этот суффикс типа
4 месяцев 100.000 г

тоже может сильно изменить формулу дистанции. Могут быть ложные срабатывания для других товаров.

Кстати этот similarity(..) какой алгоритм использует?


Это функция из расширения pg_trgm для PostgreSQL. Разбирает строки на буквенные триграммы и считает долю общих.
15 окт 21, 13:39    [22384215]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
+
    val src = """    Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г
      Пюре ФрутоНяня Груша с 4 месяцев 100.000 г
      Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г
      Фрутоняня пюре 100 г груша/яблоко
    Фрутоняня пюре 100 г груша/яблоко
    ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0
    Фрутоняня пюре 100 г груша/яблоко
    ФрутоНяня Пюре яблоко натур 100г N 1
    Фрутоняня пюре 100 г груша/яблоко
    Пюре ФрутоНяня Груша с 4 месяцев 100.000 г
      ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0
    ФрутоНяня Пюре яблоко натур 100г N 1
    Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г
      ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0
    ФрутоНяня Пюре яблоко натур 100г N 1
    Пюре ФрутоНяня Яблоко с 4 месяцев 100.000 г
      Пюре ФрутоНяня Груша с 4 месяцев 100.000 г
      ФРУТОНЯНЯ ПЮРЕ ЯБЛОЧНОЕ 100.0
    ФрутоНяня Пюре яблоко натур 100г N 1
    Пюре ФрутоНяня Груша с 4 месяцев 100.000 г"""

    val expressions : Array[String] = src.split("\n")
      .map(x => x.trim)
      .map(x => x.toLowerCase())
      .distinct

    println(s"Filtered size : ${expressions.length}")

    expressions.foreach(x => println(s">> $x"))

    import org.apache.commons.text.similarity.LevenshteinDistance
    val distFunc = new LevenshteinDistance()

    for(x <- 0 until expressions.length; y <- 0 until expressions.length) {
      if (x < y) {
        val dist = distFunc.apply(expressions(x), expressions(y))
        println(s"Levenstein distance from (${expressions(y)} - ${expressions(x)}) is $dist")
      }
    }


>> пюре фрутоняня яблоко с 4 месяцев 100.000 г
>> пюре фрутоняня груша с 4 месяцев 100.000 г
>> фрутоняня пюре 100 г груша/яблоко
>> фрутоняня пюре яблочное 100.0
>> фрутоняня пюре яблоко натур 100г n 1
Levenstein distance from (пюре фрутоняня груша с 4 месяцев 100.000 г - пюре фрутоняня яблоко с 4 месяцев 100.000 г) is 6
Levenstein distance from (фрутоняня пюре 100 г груша/яблоко - пюре фрутоняня яблоко с 4 месяцев 100.000 г) is 31
Levenstein distance from (фрутоняня пюре яблочное 100.0 - пюре фрутоняня яблоко с 4 месяцев 100.000 г) is 25
Levenstein distance from (фрутоняня пюре яблоко натур 100г n 1 - пюре фрутоняня яблоко с 4 месяцев 100.000 г) is 26
Levenstein distance from (фрутоняня пюре 100 г груша/яблоко - пюре фрутоняня груша с 4 месяцев 100.000 г) is 30
Levenstein distance from (фрутоняня пюре яблочное 100.0 - пюре фрутоняня груша с 4 месяцев 100.000 г) is 24
Levenstein distance from (фрутоняня пюре яблоко натур 100г n 1 - пюре фрутоняня груша с 4 месяцев 100.000 г) is 27
Levenstein distance from (фрутоняня пюре яблочное 100.0 - фрутоняня пюре 100 г груша/яблоко) is 18
Levenstein distance from (фрутоняня пюре яблоко натур 100г n 1 - фрутоняня пюре 100 г груша/яблоко) is 19
Levenstein distance from (фрутоняня пюре яблоко натур 100г n 1 - фрутоняня пюре яблочное 100.0) is 12
15 окт 21, 19:50    [22384350]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ы2
Member

Откуда:
Сообщений: 251
mayton, как это следует интерпретировать?

Вот другой пример:
select 
	similarity('фрутоняня пюре яблоко натур 100г n 1', 'натур пюре фрутоняня яблоко 100г n 1'),
	levenshtein('фрутоняня пюре яблоко натур 100г n 1', 'натур пюре фрутоняня яблоко 100г n 1')
;


similaritylevenshtein
122
16 окт 21, 00:09    [22384427]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
x1ca4064
Member

Откуда:
Сообщений: 1356
Ы2

Вот другой пример:
select 
	similarity('фрутоняня пюре яблоко натур 100г n 1', 'натур пюре фрутоняня яблоко 100г n 1'),
	levenshtein('фрутоняня пюре яблоко натур 100г n 1', 'натур пюре фрутоняня яблоко 100г n 1')
;


similaritylevenshtein
122

Как я понимаю, функция levenshtein просто считает РЛ для переданных строк, это не совсем верный подсчет РЛ (в контексте топика): в случае, когда строка содержит несколько слов, нужно составить матрицу расстояний между словами, потом искать по ней порядок слов, при котором сумма РЛ будет минимальной, возможно, увеличивая результат при перестановке слов.
16 окт 21, 04:15    [22384466]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
mayton
Member

Откуда: loopback
Сообщений: 52996
Да. Левенштейн - редакционное расстояние между текстами. Я точно не помню
какая формула метрики - но кажется берется удаление + перенос символов + вставка.

В данном случае similarity сработал лучше (похоже на 1-й алгоритм который я предлагал выше) без учота перемещения лексем внутри sentence.

Кажется этого-же эффекта мы могли добиться сортируя слова в фильтрации.
16 окт 21, 12:18    [22384533]     Ответить | Цитировать Сообщить модератору
 Re: Нормализация строк  [new]
Ы2
Member

Откуда:
Сообщений: 251
mayton, РЛ = вставки + замены + удаления; обычно можно настраивать вклад каждой категории.

Все это время я пытался наглядно показать, что для нечеткого поиска N-граммы — триграммы как частный случай — всегда лучше расстояния Левенштейна. Само по себе РЛ неинформативно, пока не знаешь длины строки: РЛ = 2 между «рыба» и «глыба» (заведомо разные), между «заяц плюшевый большой» и «зайц плюшевый болшой» (неграмотность и опечатка), а так же между «ваш звонок очень важен для нас» и «наш звонок очень важен для вас» (тут и триграммы бессильны).
16 окт 21, 18:39    [22384595]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Программирование Ответить