Skutecznie wyszukuj posortowany plik

Mam duży plik zawierający jeden ciąg w każdej linii. Chciałbym móc szybko ustalić, czy ciąg znajduje się w pliku. Najlepiej byłoby to zrobić przy użyciu algorytmu typu binarnego.

Niektórzy Googling ujawnili lookpolecenie z -bflagą, która obiecuje zlokalizować i wyprowadzić wszystkie ciągi zaczynające się od danego prefiksu za pomocą algorytmu wyszukiwania binarnego. Niestety, wydaje się, że nie działa poprawnie i zwraca wyniki null dla ciągów, które, jak wiem, znajdują się w pliku (są one poprawnie zwracane przez równoważne grepwyszukiwanie).

Czy ktoś wie o innym narzędziu lub strategii skutecznego wyszukiwania tego pliku?

Istnieje zasadnicza różnica między grepi look:

O ile wyraźnie nie zaznaczono inaczej, grepznajdzie wzory nawet gdzieś w linii. Dla lookstanów strony:

look - wyświetla linie zaczynające się od podanego ciągu

Nie używam lookzbyt często, ale zadziałało dobrze na trywialnym przykładzie, który właśnie wypróbowałem.

Może trochę spóźniona odpowiedź:

Sgrep ci pomoże.

Sgrep (sorted grep) przeszukuje posortowane pliki wejściowe w poszukiwaniu linii pasujących do klucza wyszukiwania i wyświetla pasujące linie. Podczas wyszukiwania dużych plików sgrep jest znacznie szybszy niż tradycyjny uniksowy grep, ale ze znacznymi ograniczeniami.

• Wszystkie pliki wejściowe muszą być posortowane zwykłe pliki.
• Klawisz sortowania musi zaczynać się na początku wiersza.
• Klawisz wyszukiwania pasuje tylko na początku wiersza.
• Brak obsługi wyrażeń regularnych.

Możesz pobrać źródło tutaj: https://sourceforge.net/projects/sgrep/?source=typ_redirect

oraz dokumenty tutaj: http://sgrep.sourceforge.net/

Inny sposób:

Nie wiem, jak duży jest plik. Może powinieneś spróbować równolegle:

/programming/9066609/fastest-possible-grep

Zawsze robię grep z plikami o rozmiarze> 100 GB, działa dobrze.

Możesz haszować plik na części, a następnie grepować tylko żądany element:

for line in $(cat /usr/share/dict/american-english | tr '[:upper:]' '[:lower:]' | sort | uniq)
do
    prefix=$(echo $line | md5sum - | cut -c 1-2)
    mkdir -p $prefix
    echo $line | gzip >> $prefix/subwords
done

wtedy odnośnik wyglądałby następująco:

    prefix=$(echo $word | md5sum - | cut -c 1-2)
    zgrep -m 1 -w word $prefix/subwords

To robi dwie rzeczy:

1. odczyt i zapis skompresowanych plików. Zazwyczaj szybsze jest ładowanie procesora (bardzo szybko) zamiast dysku (bardzo wolno)
2. hash, aby uzyskać w przybliżeniu równą dystrybucję, możesz użyć skrótu krótszego lub dłuższego, jak chcesz, aby zmniejszyć rozmiar każdego elementu (ale jeśli tak, zalecamy użycie podkatalogów zagnieżdżonych)

sgrep może dla ciebie działać:

sudo apt-get install sgrep
sgrep -l '"needle"' haystack.txt

Strona projektu http://sgrep.sourceforge.net/ mówi:

Sgrep używa algorytmu wyszukiwania binarnego, który jest bardzo szybki, ale wymaga posortowanych danych wejściowych.

Myślę jednak, że w przypadku wstawiania nie ma lepszego rozwiązania niż użycie bazy danych: /programming/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/ 33859372 # 33859372

Jeśli chcesz to naprawdę szybko (O (1) szybko), możesz zbudować zestaw skrótów, aby sprawdzić. Nie mogłem znaleźć implementacji, która pozwoliłaby mi przechowywać wcześniej zbudowany zestaw skrótów w pliku i sondować go bez konieczności odczytywania całego pliku do pamięci, więc utworzyłem własny .

Zbuduj zestaw skrótów ( -b/ --build):

./hashset.py --build string-list.txt strings.pyhashset

Sprawdź zestaw skrótów ( -p/ --probe):

./hashset.py --probe strings.pyhashset \
    'Is this string in my string list?' 'What about this one?'

… Lub z ciągiem znaków do wyszukiwania na standardowym wejściu:

printf '%s\n' 'Is this string in my string list?' 'What about this one?' |
./hashset.py --probe strings.pyhashset

Możesz wyciszyć wyjście za --probepomocą opcji -q/ --quiet, jeśli interesuje Cię tylko status wyjścia:

if ./hashset.py --quiet --probe strings.pyhashset ...; then
    echo 'Found'
else
    echo 'Not found'
fi

Aby uzyskać więcej opcji, zobacz opis użytkowania dostępny za pośrednictwem -h/--help opcji lub w dołączonym READMEpliku.