On Friday 02 December 2005 00:08, Dennis Gamayunov wrote:
Возникает вопрос: а нет ли известных функций, аналогичных хэшам, которые обладают обратными свойствами в части перемешивания:
- фиксированный размер хэша;
- гладкость, которая означает, что два набора данных будут иметь тем
более близкие значения функции в пространстве значений, чем меньше они отличаются; Причем если один текст является подстрокой другого, то значения функции для них совпадают.
Задача - сравнение двух наборов данных на похожесть. Те, кто занимался текстовым поиском и базами данных, наверняка сталкивался с этой задачей. Методы, которые я находил (расстояние редактирования, n-граммы, расстояния Левенштейна и Левенштейна-Дамерау), оперируют с функциями двух аргументов, то есть применимы только для сравнения двух текстов (строк).
А нет ли среди них таких методов, которые работают с абсолютными, а не относительными мерами? То есть сначала проецируют текст в некоторое пространство, а уже в этом пространстве оценивают расстояние между векторами.
Мне почему-то кажется, что задача не разрешима в принципе. Если у тебя есть критерий сравнения двух строк на похожесть, то с большой вероятностью этот критерий использует все символы исходных строк. Ты пытаешься заменить строку на хеш ограниченного размера, и при этом теряешь часть данных. Если изменение в одной букве может изменить результат исходного алгоритма с "похоже" на "не похоже", то сравнение хешей уже не даст правильный результат.
Единственно, что можно попробовать -- на основании специфики твоей задачи выделить "интересные" символы (например первый или последниы). Или, если речь про двой диссер, интересные классы действий, и использовать их для грубого поиска. Потом прийдтся уже делать честное сравнение строк.
- Volodya
Денис Гамаюнов.
Tech mailing list Tech@zigzag.lvk.cs.msu.su https://zigzag.lvk.cs.msu.su/cgi-bin/mailman/listinfo/tech