Skutecznie wyszukuj posortowany plik

12

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?

command-line text-processing grep Matt
źródło
W górnej odpowiedzi podano nieprawidłowe sortowanie: faktem jest, że musisz sortować za pomocą: LC_COLLATE = C sort -d, aby lookpolecenie działało poprawnie, ponieważ wygląd wydaje się ignorować ustawienia regionalne i po prostu używa C jak sortowania na stałe, otworzyłem również błąd z powodu tego mylącego zachowania: bugzilla.kernel.org/show_bug.cgi?id=198011
Sur3
look -bnie udało mi się z błędem File too large. Myślę, że stara się wczytać całą rzecz do pamięci.
Brian Minton

Odpowiedzi:

9

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.

Klaus-Dieter Warzecha
źródło
1
Plik, który muszę wyszukać, ma około 110 000 000 linii. Jeśli to zrobię egrep "^TEST" sortedlist.txt | wc -l , otrzymam 41 289 wyników. Jednak równoważne lookpolecenia look -b TEST sortedlist.txt | wc -ldają tylko wyniki z 1995 roku. Prawie zastanawiam się, czy jest jakiś błąd look.
Matt
1
@Matt Może lookużywa innych ustawień sortowania niż program użyty do sortowania pliku.
kasperd
4

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.

pamięć
źródło
2
Czy to już nie jest w askubuntu.com/a/701237/158442 ?
muru
tak, wypełniam link do pobrania ...
memorybox
Jeśli to wszystko, powinieneś edytować ten post zamiast publikować nową odpowiedź.
muru
zalecany post: sudo apt-get install sgrep aby uzyskać sgrep, sgrep w repozytoriach buntu nie jest tak naprawdę sgrep, nie jestem pewien, czy to to samo.
pudełko pamięci
0

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)
Joe
źródło
0

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

Ciro Santilli
źródło
3
The sgrep repozytoriach Ubuntu znajduje się tak naprawdę sgrep , który jest zaprojektowany do „przeszukiwania pliku w poszukiwaniu wzorca strukturalnego” i nie ma nic wspólnego z wyszukiwaniem binarnym.
ingomueller.net
0

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.

David Foerster
źródło