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