Wydajny sposób na sprawdzenie istnienia w dużym zestawie łańcuchów

Question

Mam zestaw ponad 100 ciągów znaków, każdy o długości do 63 znaków. Mam dużo miejsca na dysku i bardzo mało pamięci (512 MB). Muszę zapytać o samo istnienie i nie przechowywać żadnych dodatkowych metadanych.

Moim faktycznym rozwiązaniem jest BDBtree. Czy są jakieś preferowane alternatywy? Jestem świadomy istnienia Leveldb i Kyoto Cabinet, ale nie jestem na tyle znajomy, aby zidentyfikować zalety.

Answer 1

Jeśli wyniki fałszywie dodatnie są akceptowalne, jednym z możliwych rozwiązań byłoby użycie bloom filter. Filtry Bloom są podobne do tabel mieszających, ale zamiast używać jednej wartości mieszania w celu indeksowania tabeli zasobników, używa ona wielu skrótów do indeksowania tablicy bitowej. Bity odpowiadające tym indeksom są ustawione. Następnie, aby sprawdzić, czy łańcuch jest w filtrze, ciąg jest ponownie mieszany, a jeśli ustawione są odpowiednie indeksy, to łańcuch jest "w" filtrze.

Nie przechowuje żadnych informacji na temat ciągów, więc wykorzystuje bardzo mało pamięci - ale jeśli występuje kolizja między dwoma ciągami, nie jest możliwa żadna rozdzielczość kolizji. Oznacza to, że mogą występować fałszywe alarmy (ponieważ łańcuch nie znajdujący się w filtrze może mieszać się z tymi samymi indeksami co ciąg znaków w filtrze). Jednak nie może być żadnych fałszywych negatywów; dowolny ciąg, który naprawdę jest w zestawie, zostanie znaleziony w filtrze bloom.

Istnieje fewPythonimplementations. Nietrudno też przetasować własne; Przypominam sobie, że raz zakodowałem szybko i nieczytelnie filtr kwitnienia, który działał całkiem dobrze.

Answer 2

Powiedziałeś, że masz dużo dysku, co? Jedną opcją byłoby przechowywanie ciągów znaków jako nazwy plików w zagnieżdżonych podkatalogach. Można bezpośrednio korzystać z ciągów:

• Store "zwróciła Sears" w d/r/e/w/ sears

lub poprzez skrót napisu i w podobny sposób:

• MD5 (” zwrócił sears ') =' f010fe6e20d12ed895c10b93b2f81c6e '
• Utwórz pusty plik o nazwie f0/10/fe/6e/20d12ed895c10b93b2f81c6e.

Pomyśl o tym jako o zoptymalizowanej pod względem OS bazie danych indeksowych NoSQL opartej na hash-table.

korzyści uboczne:

• Można zmienić zdanie w późniejszym czasie i przechowywania danych w pliku.
• Można replikować bazę danych do innego systemu za pomocą rsync.