Algorithm question

[Сабина]

Знаю что есть алгоритм чтобы находить proximity of 2 strings и определять есть это варианты одного и того же стринга или нет. Например сравнение имени человека. Last name is the same, first name - вариации bill, Will etc. middle name is optional.
А нет интересно алгоритма по определению proximity of 2 lists? Скажем в списке сегодня 100 членов а завтра 102 и 99 из них совпадают, значит скорее всего речь об одном и том же списке, просто в него три члена добавили

[Alexandr]

собственно в чем проблема
фигачишь в hash-таблицу первый список, далее пробегаешь по второму и смотришь, если элемент есть в hash-таблице, то удаляешь его оттуда, если нет, то элемент добавляешь во вторую (новую) hash-таблицу. В итоге, в первой hash-таблице элементы, которые есть в первом, но нет во втором, во второй hash-таблице - элементы, которые есть во втором, но нет в первом. Соответственно, различные элементы - это объединение этих hash-таблиц
сложность O(n1 + n2) = O(n) (n1 - длина первого, n2 - второго списков)

[Alexandr]

Соответственно, для вашей задачи, нужно ввести критерий, что считать модификацией одного списка, например, изменилось не более n элементов, или изменилось не более i% элементов.

[Сабина]

Соответственно, для вашей задачи, нужно ввести критерий, что считать модификацией одного списка, например, изменилось не более n элементов, или изменилось не более i% элементов.

Это я понимаю просто был еше специальный алгоритхм для этого дела. Сейчас вспомню и напишу

[Сабина]

Нашла !
https://en.wikipedia.org/wiki/Levenshtein_distance" onclick="window.open(this.href);return false;

но в моем случае и правда не надо, просто find union of 2 sets (removeAll ) и проверить критерий

[Alexandr]

Нашла !
https://en.wikipedia.org/wiki/Levenshtein_distance" onclick="window.open(this.href);return false;

но в моем случае и правда не надо, просто find union of 2 sets (removeAll ) и проверить критерий

спасибо, тож освежу в памяти