Определение "похожести" двух массивов

[Green Mother]

Определение "похожести" двух массивов

Вкратце, задача такая:
Есть два массива, содержащих целочисленные значения. Необходимо определить их "похожесть". Под похожестью понимается некое число, отражающее наличие одинаковых значений на примерно одинаковых местах. К примеру:

$x = array(1, 5, 9, 4, 3, 8, 2, 1, 4);
$y = array(1, 5, 4, 3, 8, 2, 1, 2, 4);
$z = array(1, 10, 15, 20, 4, 4, 5, 8, 9);

у $x и $y высокий уровень похожести, а у $x и $z низкий. На ум приходит алгоритм Левинштейна, но у него сложность n*m, что в данной ситуации недопустимо, массивы большие и сравнивать много. Может кто знает, где чего почитать? Чтоб сложность порядка n+m была...

 

[Bocha]

array_diff() может это тебя устроит

 

[Green Mother]

не, array_diff это совсем другое. только что нашел levinshtein(), скорее всего ее буду юзать, встроенная побыстрей должна быть, чем кривыми ручками писаная. правда вот она для стрингов...

 

[Сергей123]

так дополняй элементы слева нулями до одинаковый длины, делай из массива строку - и вперёд

 

[Falc]

Поисковую систему что ли пишешь?

 

[Falc]

Ты вроде говорил что массивы длиные.

levenshtein()
Эта функция возвращает Levenshtein-дистанцию между двумя строками-аргументами или -1, если одна из строк-аргументов длиннее предела в 255 символов.

 

[Green Mother]

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

 

[Falc]

Тогда зачем тебе "на примерно одинаковых местах"?

 

[Green Mother]

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

 

[Falc]

Можно попробовать вести масив ($tmp) из N последних + N последующих чисел и исходном массиве.
Берем i-ы элемент из второго массива если он содержится в $tmp делаем $like++ иначе $not_like++ если после полного перебора $like/$not_like>COEF значит описания совпадают.

Подбираешь нужные N и COEF.

Поидее должно сработать.

 

[Falc]

А вообще если описаний в базе у тебя очень много (несколько тысяц или деже десятков тысяц) То построчное сканированиее с каждым из них будет очень медленым решением)
По этому лучше забить на "на примерно одинаковых местах".

И сделать так:
[SQL]
SELECT count(*) as cnt
FROM tovar_index, tovar
WHERE
tovar_index.word_id IN ($s)
AND tovar_index.tovar_id=tovar.id
AND length(tovar.description) < $size_descr
GROUP BY tovar_index.tovar_id
HAVING cnt > $word_count
[/SQL]

tovar_index - содержит проиндексированные товарные позиции в базе.
tovar - описания товаров
$s - перечисленые через запятую id слов в сравниваемом описании товара
$size_descr - длина описания сравниваемого товара
$word_count - количество слов которое должно совпасть, как правило 70% от кол-ва слов в сравниваемомо описании

Будет работать гораздо быстрее чем в ПХП проверять все массивы на частичное овпадение

 

[Green Mother]

примерно так и делаю щас.
поиском ищу наиболее подходящие тов. позиции (там запрос посложнее немного, но работает 1-3мс при базе слов в 1 млн записей, и запросе из 5-7 слов), потом уже в 5 наиболее подходящих проверяю на "похожесть", Левенштейном, первые 20-30 слов, по одному байту на слово ( crc32($word) & 0xFF - примерно так ). должно получиться довольно быстро...

 

[clevel]

я скоро тоже буду аналогичным разбором заниматься.
У меня будет реализовано немного подругому:
есть прайс, в котором мы определяем, по какому набору столбцов определять уникальность записи, например, категория+модель. Если товар не соответствует этому набору записей, то товар - новый, добавляем в базу. Если есть такой, заменяем старый товар на новый.
Да! Юзер самостоятельно для каждого прайса может определять/изменять связку уникальных столбцов.
Такой вариант может быть выходом для тебя?

 

[Popoff]

Это похоже на обычную комбинаторную задачу, в которой требуется найти пересечение двух множеств (для того, что бы найти количество совпадений). Если решать задачу на массивах, то массивы сначала удобнее отсортировать. Тогда найти количество совпадений можно будет за <=m+n сравнений. Идем одновременно по двум массивам. Если в первом например, текущий элемент=10, а во втором - 5, то идем по второму массиву, в первом стоим на месте. если во втором дошли до 10, то делаем вывод, что совпало. если дошли до числа больше 10, то на втором стоим, идем по первому.

если интересует на "примерно одинаковых местах", то во время сортировки можно тащить позиции этих элементов и в качестве критерия "одинаковости места" взять разницу позиций в исходных массивах.

не знаю, можно ли это как-то сделать с использованием БД?

 

[Green Mother]

clevel: однозначно определять равно-неравно нельзя, секретарши, которые шлют прайсы, любят ставить лишние пробелы (в том числе в уже существующие прайсы), исправлять замеченные в описаниях ошибки, в моем случае с нойтбуками править "Pentium IV" на "Pentium4" - "штоб везде одинаково было", и прочее, предусмотреть все невозможно. Разумеется, редактор, который будет заносить все в базу, должен будет сам определить какие столбцы считать описанием, какие ценой. это для него не слишком трудоемко.
Popoff, прога в зачаточном варианте уже работает. Интересует именно коэффициент соответствия старого текста описания новому. Скорей всего, оставлю левенштейна для первых 20-30 слов, сложность в пределах тысячи простеньких сишных итераций вполне устраивает.

 

[clevel]

здесь вопрос упирается в:
1.разбить описание товаров по таким столюцам. чтобы можно было потом составлять цепочку уникальных столбцов(как праймари кей в муське). Естественно, что если конфигурация компа идет все в одном поле и категория только "ноутбуки", то здесь ты прав, по другому нельзя. Но! если у тебя выделить подкатегории, анпример, тот же пентиум 4, то все проще. Да! При этом иделльый вариант - подкатегории - в виде рубрикатора, который для секретарши вв иде выпадащего списка. Удобно тем, что при изменении рубрикатора явно знаем, что изменило и товары не новые.
2.грамотно связку столбцов сделать, но это после первого пункта легко!

 

[Falc]

Originally posted by Green Mother
примерно так и делаю щас.
поиском ищу наиболее подходящие тов. позиции (там запрос посложнее немного, но работает 1-3мс при базе слов в 1 млн записей, и запросе из 5-7 слов), потом уже в 5 наиболее подходящих проверяю на "похожесть", Левенштейном, первые 20-30 слов, по одному байту на слово ( crc32($word) & 0xFF - примерно так ). должно получиться довольно быстро...

crc32($word) & 0xFF - будет достаточно часто совпадать у различных слов.

Если у тебя в словаре слова упорядочены по алфавиту, то можно воспользоваться: ( $word_id >> 4 ) & 0xFF
Тогда слова с одинаковыми начальными частями будут считаться одинаковыми, зато с совершено отличными словами будут совпадать гороздо реже .