Pamięciowy sposób przechowywania ciągów znaków

Załóżmy, że mam miliony ciągów znaków. Każdy ciąg ma wartość int. Chcę pobrać tę wartość przez ciąg wejściowy, ale nie chcę przechowywać wszystkie te ciągi, ponieważ zajmuje dużo miejsca. Nie mogę używać tablicy haszującej, ponieważ musi ona przechowywać w pamięci wszystkie lub co najmniej wiele ciągów znaków. Więc jaka jest dobra struktura danych dla mojej sprawy (nie muszę dodawać ani usuwać żadnych ciągów, mam już przygotowane dane, a odczyt jest dozwolony tylko dla operacji).Pamięciowy sposób przechowywania ciągów znaków

Źródło

2013-03-29 Neir0

Jaki język programowania? Czy istnieje wiele identycznych ciągów? –

@ jdv-Jan de Vaan Nie wszystkie napisy są niepowtarzalne. Nie sądzę, że mój specyficzny język pytania, ale wolę C#. – Neir0

Nie jest jasne, co należy zrobić. Czy potrzebujesz wyodrębnić te liczby i zapisać do innego pliku? Czy musisz wykonać z nimi jakieś obliczenia? Czy wszystko jest w porządku, jeśli kolejność danych wejściowych nie jest zachowana? –

Powód, dla którego nie należy korzystać z tabeli skrótów, nie brzmi poprawnie w oparciu o ograniczone informacje w Twoim pytaniu. Jest dość skuteczny, jeśli jest dobrze zaimplementowany. Może także mieć tę zaletę, że nie marnuje pamięci przechowującej duplikaty łańcuchów, jeśli jest to akceptowalne dla twoich potrzeb, dodatkowo zmniejszając zużycie pamięci, jeśli duplikaty są możliwe.

Możliwe jest również zapisanie skompresowanej postaci każdego ciągu znaków w tabeli mieszania, jeśli twórczy był sposób wyszukiwania. Jak długo są typowe struny?

Źródło

2013-03-29 15:26:23

Średnia długość to 10 liter. Przynajmniej nie mogę przechowywać ciągów za pomocą jednego elementu wiaderka mojego hashtable. Sądzę więc, że istnieje sposób na udoskonalenie tego podejścia. – Neir0

Użyj trie aby zapobiec przechowywania wspólne podciągi ..

Źródło

2013-03-29 15:27:10

Trie to dobry pomysł, ale znacznie wolniejszy niż hashtable. – Neir0

@larsmans Heh!Wcześniej chodziło mi o coś takiego, aby zmaksymalizować efektywność bardzo dużego schematu regex, ale teraz zastanawiam się, czy robi się to automatycznie, gdy piszowy łańcuch regex jest analizowany. Miło wiedzieć, jak się nazywa. – Nolo

a hashtable nie jest wydajną pamięcią przechowywania strun, ale – argentage

Możesz zajrzeć na Judy tree, który został zaprojektowany, aby być zarówno szybki i zwarty i ma wersję przeznaczoną dla kluczy smyczkowych. Jego wdrożenie jest dostępne pod numerem sourceforge.

Źródło

2013-03-29 23:55:36 comingstorm

Jeśli możesz wstępnie przetworzyć listę słów, spójrz na doskonałe skróty, takie jak CMPH. (gperf jest inny, ale wydaje się zoptymalizowane dla mniejszych zestawów danych).

Z Dokumenty CMPH:

Doskonałym hash odwzorowuje statycznego zestaw kluczy n do zbioru liczb całkowitych m bez kolizji gdzie m jest większe lub równe n. Jeśli m jest równe n, funkcja nazywa się minimal.

...

CMPH Biblioteka obudowuje najnowszych i bardziej efektywnych algorytmów w łatwym w obsłudze, produkcyjnej jakości, szybkiej API. Biblioteka została zaprojektowana do pracy z dużymi wpisami, które nie mieszczą się w pamięci głównej. Z powodzeniem wykorzystano go do skonstruowania minimalnych, doskonałych funkcji skrótu dla zestawów zawierających ponad 100 milionów kluczy, ...

Źródło

2013-03-30 00:17:48

Pamięciowy sposób przechowywania ciągów znaków

Odpowiedz

Powiązane problemy