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

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

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

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

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

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

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

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

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

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

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

Откуда: loopback
Сообщений: 53009
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

ЯБЛОКО ПЮРЕ


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

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

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

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

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

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

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

Откуда:
Сообщений: 252
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

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


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

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

Откуда:
Сообщений: 252
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

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

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


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

ИМХО, как выше написали, начинать надо с выделения характеристик: брэнд, тип, вкус, вес и т.д. а дальше нераспознанное можно этим способом досравнивать.
15 окт 21, 10:29    [22384092]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить