Не знаю, насколько вопрос по теме рассылки, но всё же поинтересуюсь.
Всем вам хорошо известно, что есть такие штуки как хэш-функции. Всякий хороший хэш имеет несколько полезных качеств: - фиксированный размер хеша; - необратимость, которая мне сейчас не очень интересна; - перемешивание, которое обеспечивает то, что если два набора данных отличаются в одном байте, то значения хэша для них будут сильно разнесены в пространстве значений хэш-функции.
Возникает вопрос: а нет ли известных функций, аналогичных хэшам, которые обладают обратными свойствами в части перемешивания: - фиксированный размер хэша; - гладкость, которая означает, что два набора данных будут иметь тем более близкие значения функции в пространстве значений, чем меньше они отличаются; Причем если один текст является подстрокой другого, то значения функции для них совпадают.
Задача - сравнение двух наборов данных на похожесть. Те, кто занимался текстовым поиском и базами данных, наверняка сталкивался с этой задачей. Методы, которые я находил (расстояние редактирования, n-граммы, расстояния Левенштейна и Левенштейна-Дамерау), оперируют с функциями двух аргументов, то есть применимы только для сравнения двух текстов (строк).
А нет ли среди них таких методов, которые работают с абсолютными, а не относительными мерами? То есть сначала проецируют текст в некоторое пространство, а уже в этом пространстве оценивают расстояние между векторами.
Денис Гамаюнов.
Причем если один текст является подстрокой другого, то значения функции для них совпадают.
Следовательно, любой текст, содержащий букву A, имеет один и тот же хэш? А дальше - так как для любой пары букв, одна из которых - A, декст должен иметь именно этот хэш, получаем, что единственная функция, удовлетворяющая требованиям - константа.
Следовательно, любой текст, содержащий букву A, имеет один и тот же хэш? А дальше - так как для любой пары букв, одна из которых - A, декст должен иметь именно этот хэш, получаем, что единственная функция, удовлетворяющая требованиям - константа.
О, ошибка. Значит, остаётся только требование минимальности расстояния между хешами для близких строк.
Следовательно, любой текст, содержащий букву A, имеет один и тот же хэш? А дальше - так как для любой пары букв, одна из которых - A, декст должен иметь именно этот хэш, получаем, что единственная функция, удовлетворяющая требованиям - константа.
О, ошибка. Значит, остаётся только требование минимальности расстояния между хешами для близких строк.
А тогда встаёт вопрос, какие строки считаются близкими. Например, арифметическая сумма кодов всех символов строки может удовлетворять требуемому свойству при некоторых определениях близости.
Nikita V. Youshchenko wrote:
Следовательно, любой текст, содержащий букву A, имеет один и тот же хэш? А дальше - так как для любой пары букв, одна из которых - A, декст должен иметь именно этот хэш, получаем, что единственная функция, удовлетворяющая требованиям - константа.
О, ошибка. Значит, остаётся только требование минимальности расстояния между хешами для близких строк.
А тогда встаёт вопрос, какие строки считаются близкими. Например, арифметическая сумма кодов всех символов строки может удовлетворять требуемому свойству при некоторых определениях близости.
В этом как раз один из вопросов. Насколько я понял, разные функции похожести текстов используют разные определения этой самой похожести. Близкое определение похожести к тому, что мне нужно, использует определение расстояний по n-граммам, когда смотрят число общих подстрок фиксированной длины. Но там, опять же, считают сразу расстояние, без проекции исходных текстов.
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
Vladimir Prus wrote:
Мне почему-то кажется, что задача не разрешима в принципе. Если у тебя есть критерий сравнения двух строк на похожесть, то с большой вероятностью этот критерий использует все символы исходных строк. Ты пытаешься заменить строку на хеш ограниченного размера, и при этом теряешь часть данных. Если изменение в одной букве может изменить результат исходного алгоритма с "похоже" на "не похоже", то сравнение хешей уже не даст правильный результат.
От алгоритма не требуется дать бинарный результат "похоже"/"непохоже". Допустим, хэшем будет некоторый числовой вектор. Я тогда смогу ввести эффективно вычислимую меру и вычислять расстояние между конечными векторами, а не по исходным строкам (очень медленно). Вопрос похожести будет зависеть от внешнего критерия.
Идея вот в чём: в проекте "Невод" мы строили параметрическое пространство, в которое проецировали сетевые сессии. При этом пространство строилось на основе довольно грубых статистик типа количества переданных байт в сессии на текущий момент. Были и более точные - перечислимые типы для полей сетевых пакетов фиксированного размера (флаги). Но сегмент данных фактически никак не учитывался, кроме как в статистике объёмов трафика. Хочется эти данные научиться скармливать нейросети. Сегмент данных можно представить в виде байтовой строки и сравнивать два сегмента между собой как строки. При этом если в данных содержится ассемблерный код использования какого-нибудь переполнения буффера, этот код для каждой уязвимости будет содержать похожие участки (шеллкод + заполнитель). Таким образом, если две сессии "похожи" в смысле уже используемых статистик трафика, то наличие общих подстрок в сегменте данных только увеличит похожесть. Естественно, всякие вещи типа кодирования на уровне представления (тот же BASE64) портят исходные данные приложений, поэтому перед сравнением данные нужно нормализовать - привести в тот вид, в каком они попадают в целевое приложение.
Может, кто-нибудь слышал об использовании нейросетей для распознавания/анализа текстов?
Денис.
-
Dennis Gamayunov -
Dmitry Kozlov -
Nikita V. Youshchenko -
Vladimir Prus