Najszybszy sposób przeszukiwania pliku tekstowego.

Odpowiedz Nowy wątek
2011-08-07 16:12
ziomek444444
0

Mam plik tekstowy składający się z 13 mln słów, jaka jest najszybsza metoda przeszukiwania tego dokumentu tych 13 mln słów, tak abym w jak najkrótszym czasie otrzymywał wynik zapytania czy słowo istnieje i w której linii.

To słownik? Jeżeli są ułożone alfabetycznie to możesz wyszukiwać jak drzewo. - Rev 2011-08-07 16:27
I te 13mln słów chcesz władować do pamięci na raz, aby wyszukać jedno słowo ? - Opi 2011-08-07 17:48
Mój słownik, który znalazłem w necie ma 140tys+ słów xD - xeo545x39 2011-08-07 18:03

Pozostało 580 znaków

2011-08-07 16:34
ziomek444444
0

nie to nie jest słownik, i nie są ułożone alfabetycznie.

Pozostało 580 znaków

2011-08-07 16:34
0

posortować, zamienić płaski plik na drzewo, wcisnąć do bazy


- Ciemna druga strona jest.
- Nie marudź Yoda, tylko jedz tego tosta.
Google NIE GRYZIE!
Pomogłem - kliknij

Pozostało 580 znaków

2011-08-07 17:33
0

Jeżeli nie jest posortowane to nie istnieje metoda szybsza niż sprawdzanie słów po kolei, jęsli jest posortowane to możesz szukać tak jak w książce telefonicznej. Możesz zawsze zrobić swoją wersję - posortowaną. Albo ładować do pamięci i wtedy sortować, ale nie widzę sensu robienia z tego drzewa, ja bym użył posortowanej tablicy.


Nie pisz do mnie PM o czymś co nie dotyczy bezpośrednio mnie. | Nie rozmawiaj ze mną jeśli brak Ci kultury (wystarczy że mi brakuje) | Nie jestem zły, jestem po prostu zły.

Pozostało 580 znaków

2011-08-07 17:52
Opi
0
  1. Podziel plik na 26 plików - każdy zawierający początkowe litery alfabetu: A.ini, B.ini ... Z.ini
  2. Każdy plik z pierwszą literą alfabetu, podziel na kolejne pliki o konkretnej długości: A1.ini, A2.ini ... A25.ini

Szukasz słowa: test
Wiesz, że pierwsza litera to T i jest to 4 znakowy wyraz, więc szukasz tego słowa w pliku T4.ini

Pozostało 580 znaków

2011-08-07 18:04
0

Dobry sposób Opi, a co do wyszukiwania po kolei to nie ma sensu, bo za długo zleci..


<error>There was an error during loading user signature. Please try to reboot the Universe and check again.</error>

Pozostało 580 znaków

2011-08-07 18:53
0

Dobry sposób? Chyba na marnowanie dysku.
Najlepiej zrobić plik zawierający posortowaną listę słów oddizelonych np. #13 albo #0. A potem czytać metodą dziel i zwyciężaj. Sposób Opiego to najlepsza droga do zapchania dysku.


Nie pisz do mnie PM o czymś co nie dotyczy bezpośrednio mnie. | Nie rozmawiaj ze mną jeśli brak Ci kultury (wystarczy że mi brakuje) | Nie jestem zły, jestem po prostu zły.
Nie rozumiem... Skoro mam plik i go dzielę, to ma taki sam rozmiar nie? - xeo545x39 2011-08-08 10:34
A o klastrach słyszałeś? =] - payl 2011-08-08 15:30
Słyszałem, ale w hardwarze za bardzo nie siedzę, z moich super badań wynika, że mam nawet mniejszy rozmiar tych plików łącznie niż jeden cały. - xeo545x39 2011-08-09 10:49
Bardzo ciekawe >.> Szkoda że niemożliwe. - payl 2011-08-09 14:34

Pozostało 580 znaków

2011-08-07 18:58
0

13 milinów słów = 13 000 000
Jedno słowo = około 8 znaków (bajtów)
13 000 000 * 8 = 104 000 000 bajtów
104 000 000 bajty = niecałe 100 99 GB
Chyba, że popełniłem błąd w obliczeniach.


edytowany 1x, ostatnio: Patryk27, 2011-08-07 19:17
tak, popełniłeś - Rev 2011-08-07 18:59
1 GB to 1 mln bajtów? - Wibowit 2011-08-07 19:04
104 mln b / 1024 = 102 tys kb / 1024 = 99mb - Rev 2011-08-07 19:05
104 000 000 bajty = 99Mb - payl 2011-08-07 19:05

Pozostało 580 znaków

2011-08-07 19:04
0

Autor nie napisał, że jest tam 13 mln różnych słów ale napisał, że potrzebuje dostać jako wynik linię w której dane słowo występuje, a nie tylko informację czy plik istnieje.

Jeśli masz zrobić jakąś usługę indeksującą plik to możesz np posortować go, keszować zapytania w pamięci i zastosować np filtr Blooma do odsiewania zapytań do pliku.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-08-07 19:55
0

Też jestem zainteresowany tym tematem.

Mam na dysku słownik ~35mb. Słowa w nim zapisane są mniej więcej w taki sposób:

aa
aaa
abace
abaci
abacie
abadańscy
abadańska
abadańską
abadański
abadańskich
abadańskie

Są posortowane alfabetycznie. Czy istnieje jakiś szybki sposób, na wyszukiwanie tych słów z tego słownika? (Podczas wpisywania tekstu w richedicie).
Oczywiście, aby zużycie RAM-u było minimalne.

Niektóre programy mają tą funkcję sprawdzania słów i odbywa się to u nich bardzo szybko, lecz korzystają ze słownika ~4mb a słowa zapisane w nim są w formacie typu:

a
A
aa
AA
aaa
Aalborg/Q
Aalto
AAN
AAP
Aara/M
Aare
Aargau
Aarhus
Aaron/NOosT
Aar/Q
Aasen/NOosT
ab
Ab
Abacja/M
abadanka/MmN
Abadan/Q
abadańczyk/NOqsT
abadański/bXxYc
Abaddon/O
abaka/MnN
abakanka/mMN
abakan/NQsT
  • do tego dochodzi mały pliczek *aff 240kb wewnątrz:
SET ISO8859-2
TRY aioeznrwcysptkmdłulj±gbhę¶ćóżfńĽvqxAIOEZNRWCYSPTKMDŁULJˇGBHʦĆÓŻFѬVQX

PFX b Y 1
PFX b   0         nie       .

SFX a Y 6
SFX a   e         ych       [^i]e
SFX a   e         ymi       [^i]e
SFX a   e         ym        [^i]e
SFX a   e         ch        ie
SFX a   e         m         ie
SFX a   e         mi        ie

SFX c Y 1
SFX c   i         u         i

SFX F Y 442
SFX F   c         głem      lec
SFX F   c         głe¶      lec
SFX F   c         gł        lec

.
.
.

Wie ktoś w jaki sposób to funkcjonuje?

Pozostało 580 znaków

2011-08-08 10:02
1

Wie ktoś w jaki sposób to funkcjonuje?

http://pwet.fr/man/linux/fichiers_speciaux/hunspell

ale rozwiązaniem jest po prostu użycie hunspella, a nie wynajdowanie słownika na nowo.

edytowany 1x, ostatnio: Azarien, 2011-08-08 10:05

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0