Эффективный способ хранения и сопоставления имен с большими наборами данных

java architecture full-text-search pattern-matching

570 просмотра

2 ответа

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

Предоставить словарь имен в качестве элемента конфигурации. Это выглядит более разумным, поскольку для каждого варианта использования имена могут отличаться в разных географических регионах. Я ищу лучшие практики для этого на Java. В основном это вопросы

  1. Что такое хорошая структура данных для хранения имен. Set приходит на ум в качестве первого варианта, есть ли лучшие варианты, как в базах данных памяти.
  2. Как я должен идти о поиске этих имен в больших наборах данных. Эти наборы данных действительно большие, и у меня есть возможность только читать их построчно.
  3. Любой другой вариант?
Автор: User2709 Источник Размещён: 24.10.2019 04:48

Ответы (2)


2 плюса

Посмотрите на параллельные деревья и проекты CQEngine .

Автор: Mehrdad Nurolahzade Размещён: 08.02.2016 08:46

1 плюс

Вы можете сделать это с помощью полнотекстовой индексации или онлайн-поиска.

Я бы предпочел полнотекстовое индексирование, например, с помощью Lucene . Вам нужно будет определить, как индексатор находит токены в тексте (путем определения шаблонов токенов и шаблонов dont-care).

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

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

  • Такой подход позволяет вам более гибкие строковые шаблоны.
  • Однако это не является устойчивым к изменениям набора имен (тогда полный поиск должен быть повторен).
  • Многострочный обычно принимает набор строк для поиска, но они будут хранить этот набор специфичным для алгоритма способом (большинство используют trie)

редактировать:

Эффективный поиск нескольких шаблонов / строк может быть выполнен с помощью автоматов на основе DFA.

В первый раз, когда я хотел эффективно искать в тексте, я выбрал dk.brics.automaton . Его автомат очень эффективен, но он оптимизирован для сопоставления, а не для поиска (поиск выполняется наивным способом).

Затем я переключился на свою собственную реализацию rexlex . Он основан на DFA, но немного медленнее, чем brics. Алгоритм поиска не такой наивный, как в brics, но добавляет некоторые накладные расходы.

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

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

Автор: CoronA Размещён: 09.02.2016 05:17
Вопросы из категории :
32x32