Найбільш ефективний метод пошуку по рядках - рядок, пошук

Скажіть, у мене мільйони рядків унікальних рядківпоширюється на сотні текстових файлів ("набір даних"). Тепер я хочу перевірити, чи містить будь-який із цих текстових файлів будь-який з 2 мільйонів унікальних рядків, які вказані в іншому текстовому файлі ("tofind"). Який був би найбільш ефективний шлях для цього? Деякі додаткові відомості про додаток:

• повинні бути чутливими до регістру
• рядок для пошуку відповідатиме знайденій рядку повністю (тобто це НЕ підрядка)
• кожен текстовий файл у "наборі даних" містить приблизно 700 К рядків і становить 50 Мб, хоча деякі можуть становити кілька сотень МБ.
• знову ж таки, рядки і в "наборі даних", і в "tofind" є унікальними. Індексація не допомогла.
• Немає необхідності здійснювати пошук у прямому ефірі (тобто коли хтось починає набирати текст). Я просто хочу вивести будь-які збіги в текстовий файл із збігом і файл, в якому він був знайдений.
• У мене є 32 ГБ оперативної пам’яті та i7 3930K

Мої варіанти включають використання простої командиline / batch "findstr" тощо, або, можливо, написання програми пошуку в vbscript або c # (якщо потрібно, Java або Python, але я не так знайомий з ними). ​​Що було б найефективнішим рішенням для цієї конкретної програми?

Відповіді:

Якщо у вас достатньо пам'яті для завантаження всіх струнз тонання в пам'ять, то ви можете створити набір пар, ключовим є довжина рядків, а значення - набір рядків. Завантажте всі свої рядки з tofind у цю структуру, зберігаючи їх залежно від їх довжини: Рядок із 5 символів буде зберігатися у значенні пари, що має 5 як ключ, рядок у 10 символів буде зберігатися у значенні пари маючи 10 ключових (ви можете ще більше вдосконалити це, використовуючи той самий стиль групування з першим символом, але я не виграю це описувати тут, оскільки хочу поділитися ідеєю найпростішим можливим способом).

Потім ви можете завантажити інші рядки та шукати їх виникнення. Наприклад, рядок довжиною 10 буде шукати у вашій парі, наприклад, 10 як ключ.

Якщо розмір набору даних занадто великий, то ви можете зробити те ж саме, завантаживши партію рядків за один раз, а потім очистіть структуру і відновіть її наступним пакетом.

Оскільки вам не доведеться робити це в режимі реального часудає багато широти в проектування процесу пошуку. Я не продумав це дуже ретельно, але, здається, це мені, що ви могли це зробити за кілька кроків:

Крок 1

Усуньте ці рядки з набір даних що ви знаєте, не відповідають жодній з рядків в знайти список рядків А Блум фільтр це дуже ефективний спосіб досягти цього. Він має нульову помилкову негативну швидкість, тобто якщо не потрапляє на фільтр цвітіння тоді жодна з рядків не збігається і рядок не можна усунути.

Струни, які потрапляли тоді на фільтр BloomВам потрібно перевірити, щоб ви цього не зробили отримати хибний позитив. Фільтри Блума схильні до помилкових позитивних результатів. Однак якщо ви платите пильну уважність до вибору хороших хеш-функцій та виділення достатньо великого фільтра хибнопозитивний показник може бути досить низьким.

Збережіть цю рядок і позицію в кожній рядку, де є потрапляння на фільтр Bloom рядок, де було зроблено хіт. Ця інформація передається на етап 2.

Крок 2

Перевірте рядки, які потрапляють на фільтр Bloom. Тепер вам потрібно перевірити всі 1М знайти струни за допомогою ефективної функції точного узгодження рядків. А Тріє здається, хороший кандидат для цього функція. Завантажте знайти рядок в Trie, а потім шукати його, починаючина позиції знайдений фільтром Bloom. У цей момент у вас буде або удар, і в цьому випадку було знайдено відповідність або промах, і в цьому випадку фільтр Bloom повідомив про помилковий позитив.

Примітка: Цей процес передбачає, що крок 1 може усунути значну кількість рядків з то набір даних. Якщо ви цього найбільше очікуєте набір даних рядки містять відповідність у знайти потім це може бути не вартим зусиль.