Есть множество из N > 10^6 строк текста а так же функция distance(x,y), которая может за O(length(x)*length(y)) определить степень сходства между двумя строками x и y. Необходимо найти все пары строк (x,y) из данного множества, таких, что distance(x,y) < k, где k -- заданная константа, за время, меньшее чем полиномиальное.

Здравствуйте, sch, Вы писали:

sch>Есть множество из N > 10^6 строк текста а так же функция distance(x,y), которая может за O(length(x)*length(y)) определить степень сходства между двумя строками x и y. Необходимо найти все пары строк (x,y) из данного множества, таких, что distance(x,y) < k, где k -- заданная константа, за время, меньшее чем полиномиальное.

В общем случае задача не имеет решения. Для оптимизации нужна информация о функции distance(x,y).

Здравствуйте, sch, Вы писали:

sch>. Необходимо найти все пары строк (x,y) из данного множества, таких, что distance(x,y) < k, где k -- заданная константа, за время, меньшее чем полиномиальное.
Меньше, чем полиномиальное -- это сильно Как уже правильно отметил Mystic, чудес на свете не бывает. Скажем, если distance = 0, k > 0, то ответом будут все возможные пары, так что время выписывания ответа будет пропорционально N^2.

Обычно в таких случаях считают алгоритм (точнее, структуру данных) удачным, если он дает ответ за время O(t + polylog(n)), где t -- длина ответа. Вроде бы изучены не так много случаев, когда эта оценка достигается. Скажем, даже решения для ортогональных запросов (выдать точки из заданного гиперкуба) уже нетривиальны при размерности выше 1.

sch wrote:
> Есть множество из N > 10^6 строк текста а так же функция distance(x,y),
> которая может за O(length(x)*length(y)) определить степень сходства
> между двумя строками x и y. Необходимо найти все пары строк (x,y) из
> данного множества, таких, что distance(x,y) < k, где k -- заданная
> константа, за время, меньшее чем полиномиальное.
меньше чем полиномиальное отночительно чего N? или длины строк L
для пары строк есть возможность оценить расстояние редактирования за
линейное время — поищите "Using Q-grams in a DBMS for Approximate String
Processing"
по Q-граммам также можно для каждой строки найти ближайшие используя
обратный индекс за время значительно меньшее чем O(N), точнее O(pN), где
p — вероятность того, что строки похожи

GW>меньше чем полиномиальное отночительно чего N? или длины строк L
GW>для пары строк есть возможность оценить расстояние редактирования за
GW>линейное время — поищите "Using Q-grams in a DBMS for Approximate String
GW>Processing"
GW>по Q-граммам также можно для каждой строки найти ближайшие используя
GW>обратный индекс за время значительно меньшее чем O(N), точнее O(pN), где
GW>p — вероятность того, что строки похожи

Спасибо большое.
"Есть многое на свете, друг Горацио..."