Как найти все палиндромы в терабайтном файле?

Question

[xperious]

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

Comments

[xperious]

Лентяй, ну, пускай слова просто построчно записаны

[sim3x]

Читать построчно
Вносить информацию в Postgresql
Делать поиск по бд

Но расчитывать на большую скорость не стоит

Еще можно попробовать использовать shpinxsearch
Или даже начать с него

[xperious]

Лентяй, да я вот думаю: а как эффективно искать в нескольких файлах? не в цикле ж каждый с каждым сравнивать?

[xperious]

Лентяй, а бд как работает?) меня именно алгоритм интересует

[xperious]

Лентяй, работал... но алгоритмами, которые в основе, не интересовался

[SeptiM]

Для поиска числа уникальных элементов можно воспользоваться алгоритмом HyperLogLog. Подробнее здесь: antirez.com/news/75

Answer 1

[Данил]

Для Python можно использовать библиотеку pandas. Pandas позволяет загружать файл итеративно. Выглядит примерно так:

import pandas as pd

chunks = pd.read_csv('path_to_file',  chunksize=150000)
for chunk in chunks:
    # do whatever you want
    pass

Answer 2

[Иван Корюков]

В большинстве ЯП поддерживается чтение некоторого количества байт с определённого места из файла.
Т.е. можно открыть файл (не считать его весь, а только открыть), после этого в цикле читать по N байт и итерировать по ним. Дальше уже дело за алгоритмом, который принимает по одному символу и пытается в потоке символов вычислить палиндром. Т.е. это машина состояний. Думаю там нужен стэк ограниченного размера с выталкиванием самых старых символов при поступлении новых.

// псевдокод
file = open("my_big_file.txt","r");
buffer = byte[1024];
palindrome_scanner = new PalindromeScanner(4, 64); // min and max palindrome size
while(canRead($file)){
    buffer = fread(file, &buffer);
    for(int i=0; i<2024; i++){
        palindrome_scanner->next(buffer[i]);
    }
}

Answer 3

[Владимир Олохтонов]

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

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

Если слово является палиндромом - пишем его в другой файл.

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

На практике алгоритм можно сильно ускорить если читать и писать строки не по одной, а батчами - ценой будет увеличенное потребление памяти.

Answer 4

[SeptiM]

https://arxiv.org/abs/1506.04862

Там структура данных, линейная по памяти с суффиксным бором и деревом. Очень эффективная. Остается, правда, придумать, как ее на терабайт отмасштабировать.