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

Question

Моя компания поддерживает язык, специфичный для домена, который синтаксически напоминает язык формул Excel. Мы рассматриваем возможность добавления новых встроенных в язык. Один из способов сделать это - определить подробные команды, которые многократно используются в нашей кодовой базе. Например, если мы видим, что люди всегда пишут одну и ту же команду из 100 символов, чтобы обрезать пробелы в начале и конце строки, это говорит о том, что мы должны добавить функцию trim.

Просмотр списка часто используемых подстрок в базе кода будет хорошим началом (хотя иногда часто используемые команды отличаются на несколько символов из-за разных имен используемых переменных).

Я знаю, что для этого существуют хорошо разработанные алгоритмы, но сначала я хочу посмотреть, смогу ли я избежать повторного изобретения колеса. Например, я знаю, что эта концепция является основой многих алгоритмов сжатия, так есть ли модуль сжатия, который позволяет мне получать словарь частых подстрок? Любые другие идеи будут оценены.

Answer 1

Я думаю, вы могли бы использовать существующий полнотекстовый индексатор, такой как Lucene , и реализовать свой собственный анализатор и Tokenizer , специфичный для вашего языка формул.

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

Вот небольшая статья, с которой можно начать:

Lucene Analyzer, Tokenizer и TokenFilter

Answer 2

Сопоставление строк - это просто низко висящий фрукт, очевидные случаи.Более сложные случаи, когда вы делаете похожие вещи, но в другом порядке.Например, предположим, что у вас есть:

X+Y
Y+X

Ваш подход сопоставления строк не поймет, что это эффективно то же самое.Если вы хотите пойти немного глубже, я думаю, что вам нужно проанализировать формулы в AST и сравнить их.Если вы это сделаете, вы увидите, что дерево на самом деле одно и то же, поскольку бинарный оператор '+' является коммутативным.

Вы также можете применять правила сокращения, чтобы вы могли вычислять сложные функции в более простые, например:

(X * A) + ( X * B)
X * ( A + B )

Это тоже самое!Сопоставление строк не поможет вам там.

1. Разбор в AST
2. Сокращение и оптимизация функций
3. Сравнение полученного AST с другими AST

Если вы найдете совпадениезатем замените их вызовом общей функции.

Answer 3

Возможно, вы захотите взглянуть на генераторы облаков тегов .Я не мог найти источник в минуту, которую я потратил на поиск, но вот он-лайн: http://tagcloud.oclc.org/tagcloud/TagCloudDemo, который, вероятно, не будет работать, поскольку он использует пробелы в качестве разделителей.