Алгоритмы поиска в потоке XML

Question

Я ищу предложения по алгоритмам / методам для широкого поиска в потоковом XML-документе.

<foo>
   <bar name="aaa" >
       <grah name="aab" />
        ..
   </bar>
   <bar name="bbb" />
   <bar name="ccc" />
   <bar name="ddd" />
   <bar name="eee" />
... up to 10,000 entries
</foo>

Количество элементов 1-го уровня вне моего контроля. Использование xml также вне моего контроля. Я могу предварительно обработать XML, я могу индексировать XML, но я не могу (в обозримом будущем) загрузить весь XML-документ в память для каждого запроса.

В настоящее время я выполняю поиск с использованием возможности потокового чтения libxml для выполнения этой задачи. Он потребляет более или менее фиксированный объем оперативной памяти / запроса и очень быстро реагирует, как правило, на строки размером менее 3 тыс., И кеширование наиболее популярных результатов помогает, но на каком-то этапе поражается почти каждый элемент верхнего уровня.

В последнее время нам приходилось иметь дело с рядом действительно больших файлов, в которых элементы уровня 1 имели размер до 10000 элементов, а совпадение ближе к концу недопустимо в отношении ответа сервера.

До сих пор я видел Introselect и Quickselect, которые могут уменьшить пространство поиска до чего-то разумного. Я думал, что посмотрю, есть ли какие-то другие идеи или алгоритмы, которые я пропустил до того, как начал писать код.

Answer 1

Вы не объясняете подробно, каковы требования к поиску или как будет выглядеть текст для поиска.Я предполагаю, что сам по себе XML не представляет интереса и что анализ потока, который вы выполняете с помощью libxml, может быть сделан для непрерывного построения объектов, в которых данные из XML были уточнены и облегчены для поиска.

Конечно, вы можете просто вставить XML-документ в базу данных XML, например eXist .Это очень гибко, если вы хотите сохранить исходный XML, но если вы можете выбросить это, я бы искал другие способы хранения только сути XML-документа;данные, которые нужно искать.

Поскольку вы пишете, что XML можно предварительно обрабатывать, я также предполагаю, что XML не очень часто меняется.Если эти предположения верны, вы можете проиндексировать текст, который вы хотите найти, в базе данных, ориентированной на поиск, например Lucene .Конечно, вы можете создать алгоритм поиска самостоятельно, но, поскольку есть решения с открытым исходным кодом, которые делают это (с кэшированием запросов и прочее), я рекомендую вам взглянуть на некоторые из существующих решений.

Еслисами поиски не сильно различаются, вы также можете создавать объекты JSON из данных в XML и сохранять их в базе данных документов (например, MongoDB или CouchDB ) с предварительно определенными индексамив нем в значительной степени содержится ответ на запросы, которые вы хотите выполнить в памяти.

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