Не знаю, насколько вопрос по теме рассылки, но всё же поинтересуюсь.
Всем вам хорошо известно, что есть такие штуки как хэш-функции. Всякий
хороший хэш имеет несколько полезных качеств:
- фиксированный размер хеша;
- необратимость, которая мне сейчас не очень интересна;
- перемешивание, которое обеспечивает то, что если два набора данных
отличаются в одном байте, то значения хэша для них будут сильно
разнесены в пространстве значений хэш-функции.
Возникает вопрос: а нет ли известных функций, аналогичных хэшам, которые
обладают обратными свойствами в части перемешивания:
- фиксированный размер хэша;
- гладкость, которая означает, что два набора данных будут иметь тем
более близкие значения функции в пространстве значений, чем меньше они
отличаются; Причем если один текст является подстрокой другого, то
значения функции для них совпадают.
Задача - сравнение двух наборов данных на похожесть. Те, кто занимался
текстовым поиском и базами данных, наверняка сталкивался с этой задачей.
Методы, которые я находил (расстояние редактирования, n-граммы,
расстояния Левенштейна и Левенштейна-Дамерау), оперируют с функциями
двух аргументов, то есть применимы только для сравнения двух текстов
(строк).
А нет ли среди них таких методов, которые работают с абсолютными, а не
относительными мерами? То есть сначала проецируют текст в некоторое
пространство, а уже в этом пространстве оценивают расстояние между
векторами.
Денис Гамаюнов.
