Идентификация строк (hash? не hash?). Не хватает матчасти.

хэш от «номер + содержимое строки» - немного лучше. немного

осталось только придумать обратную фушкцию, чтобы по этому хэшу найти-таки нужную строку )

Если строка сдвинется, то перестанет по этому алгоритму идентифицироваться вообще.

так тебе надо наоборот? чтобы она независимо от положения в файле могла быть идентифицирована? ну, такоэ…

надо.

При этом лучше всего либо опробированное решение, либо теория на основании которой это можно вдумчиво сделать…

в качестве метрики «вас тут (не) стояло» можно использовать контекст - соседние строки сверху и снизу от изучаемой.

для проверки схожести - например, google://расстояние+левенштейна

Удовлетворите любопытство, вам для чего такое понадобилось?

информацию о покрытии тестами, или комментарии

Как-то не вяжется с требуемой реализацией.

Посмотрите, как подсвечиваются diff’ы в коммитах, может это то что надо.

есть dоxygen, который можно использовать без фанатизма - только для индексирования и анкеров.

То есть побыстрому парсить выхлоп doxygen на тему «вот класс/шаблон/метод», а нету ли к нему внешних заметок. Он ведь и в xml индексы делает и даже sqlite.

И собственный тег можно задать а-ля «\mark» и по индексу находить все или конкретный mark.

если нельзя текст курочить - тогда по семантике или синтаксису. Сильно вкурить clang, а лучше (проще+быстрее) взять любой syntax highligher - они почти все умеют отдавать xml; и помнить/строить свои внешние метки как XPath,XQuery по ним.

Списочек: https://en.wikipedia.org/wiki/String_metric

Списочек: https://en.wikipedia.org/wiki/String_metric

Спасибо, да… Я этот список отталкиваясь от «Levenshtein distance» упомянутый выше уже нашел…

Более меня забавляет, что не находится вообще никакой информации о функциях сверки, позволяющих с точностью до коллизий оценивать расстояние между исходными элементами по значениям функций свертки…

Должен же хоть кто-то был с этим играться…

Прошаренный коллега подсказал ключевое слово «Locality-Sensitive Hash»

Какую-то херню и костыли вы хотите. Если у вас задача идентифицировать не строки а функции\методы (ну вы же не строки тестируете в коде, ну в самом деле же) то вам нужно парсить не строки, а сами сущности. Например функции\методы.

LLVM в зубы. А вообще выглядит так, как будто вы делаете какой-то самописный костыль для покрытия тестами. Вам сюда: https://www.browserstack.com/guide/code-coverage-tools

нет, у меня задача сделать контентно-зависимый идентификатор строки. Вне зависимости от того код ли это на Си или Война и Мир.

никакой информации о функциях сверки,

Поправка: «функциях свёртки»

Перенося различную мета-информацию (например информацию о покрытии тестами, или комментарии) между немного разными комплектами исходников

Я, честно говоря, так и не понял, зачем.

Это даже гит не смог реализовать это без глюков. Какую задачу вы решаете? То что вы сказали это попытка что-то решить, а не сама хадача

у меня задача сделать контентно-зависимый идентификатор строки

взяли хэш от всех параметров контекста.

идентификатор строки? да.

контекстно-зависимый? да.

все, профит, не?

а если «не» - ты от нас что-то скрывааааешь!

LSH на arxiv.org, но не думаю, что он тут поможет.

Ну ты внятно задачу-то свою сформулируй.

Например, для такого определения ответ тривиален:

Назовём строкой упорядоченное множество символов, оканчивающихся символом '\n'. Существует ли функция отображения множества строк на множество натуральных чисел?

Назовём строкой упорядоченное множество символов, оканчивающихся символом ‘\n’. Существует ли функция отображения множества строк на множество натуральных чисел?

такое, чтобы по результатом вычисления некой функции D() от полученных вышеуказанным способом двух натуральных чисел, можно было бы с точностью до коллизий оценить расстояние Липштейна между их оригиналами…

LSH на arxiv.org, но не думаю, что он тут поможет.

arxiv.org хорошая идея, спасибо. Сам не додумался. Тоже не уверен что поможет, но не значит что не надо пробовать.

Это даже гит не смог реализовать это без глюков.

А известно как он это пробовал реализовать? Можете показать пальцем?

у меня задача сделать контентно-зависимый идентификатор строки

взяли хэш от всех параметров контекста.

Не контекста, а контента. Контент при этом может быть вырожденным, брать хеш только от него без мазы.

Пусть у тебя есть класс. В классе есть метод. В методе есть, ну там, условие. Внутри условия есть присваивание.

Тогда строка обозначается как class(classname).method(methodname).if(ifNumber).assignment(a=5)

И вне зависимости от количества строк в файле, переноса в другой файл, переделывания даже части самого класса, такой идентификатор меняться не будет.

Я правильно понял, чего тебе надобно?

С Толстым сложнее, потому что там надо будет опираться на главы и абзацы, а они в общем случае могут уехать. Если же текст не сильно меняется, человечество уже пару тысяч лет использует указатели вида Мф:5.27.

Я правильно понял, чего тебе надобно?

Нет.

Мне надо конструкцию вида

[HASH_N-1]-[HASH_N-2]-[HASH_N+1]-[HASH_N+2]-[LSH_N]-[HASH_N]

[HASH_N] - хеш самой строки

[HASH_N+-n] - хеши соседей чтобы зафиксирвоать в каком окружении строка находится (если HASH_N дает коллизию)

[LSH_N] - Locality-Sensitive Hash самой строки чтобы можно было найти строку подвергшуюся редактированию (тогда HASH_N уже не поможет)

Может быть еще и для контекста добавить LSH. А может быть только на одних LSH жить…

Но самое главное, я хочу теории… Чтобы не на пальцах это все прикидывать, а стоять на плечах великих. И уже там прикидывать на пальцах…

Выше люди тоже недоумевают и похоже никто ответа не получил.

А какую задачу, собственно, хотим решить? Вот нашли вы искомую хеш-функцию, а делать вы с ней что потом будете?

Метаиформацию информацию с ним ассоциировать:

• Количество проходов по строке при запуске тестов (покрытие).

• Букмарка с комментарием.

• Информация выданная статическим анализатором.

Мало ли какую еще метаинформацию захочется прикрепить к конкретной строке текста, а потом переносить между разными версиями…

А длинна идентификатора строки должна быть фиксирована? =)

По-моему из БД, в которой отдельная запись и есть «файл», вы никак не сделаете БД в которой записью будет «строка файла».

Так-то были такие файловые системы раньше. В той же Pick Operating System.

Но там целая ОС вокруг этого по сути крутилась.

Тогда строка обозначается как class(classname).method(methodname).if(ifNumber).assignment(a=5)

При таком подходе куски программы:

x = x + 2;
x = x * 2;

и

x = x * 2;
x = x + 2;

считаются идентичными. Тоже не хорошо, наверное.

Но самое главное, я хочу теории… Чтобы не на пальцах это все прикидывать, а стоять на плечах великих. И уже там прикидывать на пальцах…

В 1С проверка идёт по «нормализованным строкам». То есть без учёта пробелов до и после.

И блоки сравниваются по функциям + дополнительно отслеживается переименование функций (если старое имя пропадает, ищет среди новых, вдруг есть с очень похожим телом).

Даёт результаты заметно лучше, чем у git и kdiff3.

Если переводить на твою задачу, то для каждой строки вводишь GUID и при изменении текста тебе нужен старый текст и новый. В новом ищешь сопоставления строк к старому. Если строка в старом тексте не найдена, даёшь ей новый GUID.

Если про текст вообще ничего сказать нельзя, бери алгоритм из diff.

Aceler уже предложил в каком то виде.

Универсальное может что то и существует, я не слышал. Но для програмного кода, на правах идеи.

Надо строить абстрактное дерево как это делают компиляторы. Это позволит соотносить строки с узлами дерева, как бы они не сдвигались.

Т.е. если хочется понимать что это одна и та же строка «по смыслу» - ну, надо вычислять этот смысл, собственно. Мне так кажется.

Комменты в программе связывать с узлом программы. Если хочется каких-то фич для текста дополнительных - добавлять их из работы с текстом.

А длинна идентификатора строки должна быть фиксирована? =)

Не обязательно.

Более того, вырожденный случай, когда идентификатор равен строке или содержит ее – рассматриваем, как минимум для теоретической ясности.

Но для C++ AST-дерево будет зависеть от того, как разрезолвятся макросы и шаблоны.

да, по большому счёту нужно писать бекэнд для компилятора, я понимаю.

ну ТС ведь хочет стоять на плечах гигантов :)

Я не предлагал решение. Я понять пытался, что ему надо :-)

похоже вам поручили рисовать 7 перпендикулярных линий, смысл хеша как раз в зависимости от внутреннего состояния, а не от внешнего. Задачи локализования строки решаются как «полный путь файла + номер строки» или бывает еще «неймспейс + сигнатура»;

ключевые слова – diff.

читать – https://neil.fraser.name/writing/diff/myers.pdf

читать – https://neil.fraser.name/writing/diff/myers.pdf

Круто.

А как была добыта ссылка на этот документ?

Если у вас задача идентифицировать не строки а функции\методы (ну вы же не строки тестируете в коде, ну в самом деле же) то вам нужно парсить не строки, а сами сущности. Например функции\методы.

LLVM в зубы.

Совершенно не обязательно. Тот же git-diff использует обычные регулярки для отслеживания границ функций.

Git diff прекрасно ломается, считая что какой-то файл «перемисан на 90%», или «перемещен», когда вы создаете рядом другой. Кучу раз ломались скрипты из-за этого

Да, но это из-за используемой метрики «похожести», а не из-за неточного разделения диффов по функциям.

Ну и, возможно, из-за того, что git явно не записывает информацию о перемещениях/переименованиях, а восстанавливает её на ходу. Но у этого подхода есть и определённые плюсы.

Круто.

Есть круче. :)

https://github.com/maxbachmann/rapidfuzz-cpp

Не особо понял чего тебе нужно.

По поводу расстояний между строками тебе выше уже ответили, правда учти, что некоторые метрики это NP-полные задачи…

Примеры реализации тоже вроде бросили: git, diff…

Но как тебе это все поможет? Ведь с т.з. тестирования, если код изменился, то его надо снова тестировать, единственное, что ты можешь выкинуть из строк – это комментарии, поэтому тебе надо сохранять информацию о неизменности многострочного блока. Что приводит к мысли, что у тебя есть просто поиск вхождения подстроки (оттестированные блоки) в строку (весь код).

Круто.

Есть круче. :)

https://github.com/maxbachmann/rapidfuzz-cpp

Слон плохой, справка хороший!

Там есть папка docs/literature, вот в ней судя по всему круто, да…

• Количество проходов по строке при запуске тестов (покрытие).

• Информация выданная статическим анализатором.

Йок, не надо это переносить, это надо заново вычислить с кешем.

Расстрелять ногу.

Возможно тебе надо это https://en.wikipedia.org/wiki/Locality-sensitive_hashing