Чтение в основном структуры данных для сжатия и поиска исходного кода
Предположим, у вас много исходного кода (например, 50 ГБ +) на популярных языках (Java, C, C ++ и т. Д.).
Потребности проекта:
-
сжатие исходного кода для уменьшения использования диска и дискового ввода-вывода
-
индексировать его таким образом, чтобы конкретный исходный файл можно было извлечь из сжатого источника без распаковки всего
-
время сжатия для всей кодовой базы не важный
-
время поиска и поиска (и использование памяти при поиске и извлечении) имеют важное значение
Этот SO ответ содержит потенциальные ответы: Каковы менее известные, но полезные структуры данных?
Однако это всего лишь список возможностей — я не знаю, как эти структуры на самом деле оценивают требования, перечисленные выше.
Вопрос: каковы структуры данных (и их реализации), которые будут хорошо работать в соответствии с вышеупомянутыми требованиями?
Решение
Основной структурой данных, используемой для поиска, является перевернутый список. К счастью, вам не нужно реализовывать это самостоятельно. Lucene это широко используемый инструмент поиска, который работает с инвертированными списками внутри.
Используя Lucene, вы можете создать документ с несколькими поля. Идея состоит в том, что некоторые из этих полей будут поиск со стандартными запросами типа ключевых слов.
Я реализовал утилиту поиска исходного кода, которую я сейчас кратко опишу в следующих параграфах. Весь исходный код хранится в виде неиндексируемого поля с именем «code» (вы можете изменить исходный код для хранения сжатой версии).
Что касается поисковой части, обратите внимание, что ключевыми словами, которые вы собираетесь использовать для поиска, могут быть имена функций, классов, пакетов или переменных. Это также могут быть слова из комментариев и так далее. В моей реализации я извлек эту информацию из аннотированного синтаксического дерева Java (AST). Вы можете сделать то же самое для других языков, используя соответствующий синтаксический анализатор для создания AST.
Другая возможность — это парадигма запрос-пример (QBE), где вы можете использовать небольшой фрагмент кода для поиска примерно похожих фрагментов из вашей индексированной базы кода. Это особенно полезно для обнаружения повторного использования исходного кода и плагиата, основной цели, для которой я разработал инструмент.
Страница проекта Вот. Я называю это YASOCS (еще один поисковик кода источника).
Поиск очень быстрый, так как использует перевернутый список. Вы также можете использовать Люк (визуализатор индекса Lucene с открытым исходным кодом), чтобы «увидеть» индекс самостоятельно и выполнить тестовые запросы с помощью интерфейса.
Другие решения