LINUX.ORG.RU

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

 


1

4

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

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

   }

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

Далее вопрос, не должен ли идентификатор содержать какую-то метрику позволяющую как-то оценить дельту между двумя строками по идентификатору. Чтобы можно было сказать что эта строка является немного отредактированной версией вот той. Возможно ли это чисто математически?

Нет ли какой-то метрики позволяющий оценить насколько строка «самобытна». Это скобка среди пробелов, или много разных слов. Чтобы можно было

Не решались ли подобные задачи ранее? Вдруг в недрах какого-нибудь git’а все уже придумано?

Где-бы почитать про разные метрики которые можно применить к текстовым объектам, в том числе с целью их идентификации… По каким ключевым словам искать? Мне однозначно не хватает базовой теории, а интернет полон искусственного интеллекта и блокчейна…

★★★

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

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

aol ★★★★★
()
Последнее исправление: aol (всего исправлений: 1)
Ответ на: комментарий от shaplov

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

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

aol ★★★★★
()

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

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

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

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

vvn_black ★★★★★
()
Последнее исправление: vvn_black (всего исправлений: 2)

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

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

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

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

MKuznetsov ★★★★★
()
Ответ на: комментарий от dataman

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

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

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

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

shaplov ★★★
() автор топика

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

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

PPP328 ★★★★★
()

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

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

Nervous ★★★★★
()
Ответ на: комментарий от shaplov

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

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

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

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

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

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

olelookoe ★★★
()

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

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

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

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

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

shaplov ★★★
() автор топика
Ответ на: комментарий от dataman

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

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

shaplov ★★★
() автор топика
Ответ на: комментарий от olelookoe

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

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

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

shaplov ★★★
() автор топика

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

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

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

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

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

Aceler ★★★★★
()
Ответ на: комментарий от Aceler

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

Нет.

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

[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 жить…

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

shaplov ★★★
() автор топика
Ответ на: комментарий от anonymous7

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

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

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

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

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

shaplov ★★★
() автор топика

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

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

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

Toxo2 ★★★★
()
Ответ на: комментарий от Aceler

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

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

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

и

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

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

monk ★★★★★
()
Ответ на: комментарий от shaplov

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

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

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

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

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

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

monk ★★★★★
()
Ответ на: комментарий от shaplov

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

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

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

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

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

AndreyKl ★★★★★
()
Последнее исправление: AndreyKl (всего исправлений: 1)
Ответ на: комментарий от LINUX-ORG-RU

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

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

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

shaplov ★★★
() автор топика

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

Syncro ★★★★★
()
Ответ на: комментарий от PPP328

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

LLVM в зубы.

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

annulen ★★★★★
()
Последнее исправление: annulen (всего исправлений: 1)
Ответ на: комментарий от PPP328

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

annulen ★★★★★
()

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

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

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

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

soomrack ★★★★★
()
Последнее исправление: soomrack (всего исправлений: 1)
Ответ на: комментарий от shaplov
  • Количество проходов по строке при запуске тестов (покрытие).

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

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

t184256 ★★★★★
()
23 декабря 2023 г.