Witam, mam za zadanie napisać program (w konsoli) który ma za zadanie sprawdzenie ortografii tekstu za pomocą pliku słownikowego.
Chciałem porównać każde słowo ze sprawdzanego tekstu z elementami słownika. Jeśli sprawdzane słowo znajdowałoby się w słoniku to oznacza ze słowo jest poprawnie napisane.
Mój problem polega na tym, że nie wiem jak napisać taki program, żeby był w miare szybki. Znalazłem słownik który ma prawie 3 miliony słów. Ale zanim zostanie cały słownik przeleciany to wieki miną. Myślałem też zeby podzielić słownik na kawałki tak, żeby program porównywał sprawdzane słowo ze słowami słownika które zaczynają sie na te samą literę. W sumie powino być lepiej ale jak podzielić ten słownik? Program mam napisać z wykorzystaniem list. Czy poszczególne słowa ktore zaczynają się na te samą litere mam wczytywać do oddzielnej listy?
Czy ktoś spotkał się może z podobnym problemem? Ktoś może ma jakiś ciekawy pomysł?
Proszę o odpowiedz i pozdrawiam
Użyj jakiegoś sensownego drzewa binarnego. W najgorszym przypadku przejechanie przez cały słownik będzie wymagało 22 (log2 z 3000000) porównań.
Sposób jest kilka:
- Szukanie połówkowe, najłatwiejsze w implementacji: strzelasz losowo dokładnie w polowę słownika i sprawdzasz czy twój szukany wyraz jest w jednej czy w drugiej połówce (za miejscem w które strzeliłeś lub przed nim) i nastepnie strzelasz w środek tej połówki (oczywiscie sprawdzasz tez przy okazji czy nie trafiłeś w twój wyraz akurat). W ten sposób z 3 milionów wyrazów jesteś w stanie znaleźć swój w max 22 strzałach
- jw. jakies drzewo binarne
- tablica z hashowaniem, jako hash np. xorowanie fragmentów słowa. To akurat najszybsza metoda, bo przy dobrym hashowaniu będziesz miał max 3-4 szukania w tablicy, ale i to tylko w przypadku kiedy dla dwóch różnych słów będzie ten sam hash. Konflikty mozesz rozwiązywać na zasadzie listy. Tzn hash wskazuje na początek listy elementów o tym hashu i potem przeglądasz już tylko ta listę.
// "strzelasz losowo dokładnie w polowę" - genialne - R
// edit : nie wiem skąd mi się wzięło tam to "losowo" :D
A Czy ktoś może mi jeszcze powiedzieć jak np wczytać do stringa n-tą linie z pliku? Mam kod:
string adres="d:\\\\a.txt";
ifstream plik(adres.c_str());
string linia;
int n=150000;
plik.seekg(n,ios_base::beg);
getline(plik,linia);
Dlaczego to coś nie działa?
A dlaczego nie odróżniasz linii od bajtów?
Ano masz racje... Nie doczytałem troche...
Ale i tak jak wstawie ileś tam bajtów zeby przeskoczył to i tak nie działa. Non stop jest w tym samym miejscu (na początku pliku).
W takim razie jak to zrobić? Jak wczytać np 1000 linie z pliku?
popraw indeksowanie tak, by zwracało ci pozycję w pliku w bajtach, a nie numer linii. Domyślam się, że do tego słownika zastosowałeś hashtable, które zwraca numer linii, a powinieneś zapamiętywać numer bajtu.
Nie zastosowałęm żadnego hashtable ani niczego. Po prostu mam plik tekstowy w którym w każdej linijce jest jeden wyraz. I chce odczytać linie która jest n/2 (gdzie n to ilość wszystkich lini). Napisałem juz funkcje która zwraca ilość tych lini. I teraz muszę znaleźć sposób żeby właśnie przeskoczyć do tej n/2 lini... Kompletnie nie wiem jak to zrobić... Jak sprawdzić ile bajtów od początku pliku znajduje sie ta linia...
Tak w ogóle chce to zrobić sposobem pierszym jaki zaproponował Shalom. Bo te drzewa itd trzeba wczytać do pamięci. Wtedy program zżera strasznie duzo tej pamięci... Powiedzmy że mój słownik ma ponad 30mb...
Proszę pomóżcie mi to zrobić... Może ktoś napisze mi kawalek kodu ale poda funkcje jaką można by było użyć...
Trzeba było zrobić metodą 3 jest najszybsza i w miarę prosta.
Jeśli chcesz skoczyć do jakiejś linii w pliku musisz zapamiętać początek każdej linii. Czyli przy liczeniu liczb linii musisz pobierać pozycję wskaźnika odczytu i go zapamiętać.
No dobra, 30mb pamięci. Ale dzisiaj 2-4gb to jest standard, wiec nie rozumiem czemu tak ci zal tych 30.
A zdajesz sobie sprawę o ile szybsze będzie szukanie w tablicy wczytanej do pamięci, od szukania w pliku?
Ja bym jednak na twoim miejscu wybrał szybkość zamiast troche większego zużycia pamięci.
@Shalom: niewiele zyskasz, przy wyszukiwaniu binarnym to i tak jest tylko parę porównań. Do tego typu zastosowań jakichś ultra szybkich algorytmów nie musisz mieć. Zresztą chyba nie wziąłeś pod uwagę tego, że konstruowanie takiej tablicy trochę trwa.
@Pepis: na forum www.winapi.org był podobny temat, dałem tam przykładowy kod takiego słownika.
Na oko konstruowanie odpowiedniego drzewa\hashtablicy trwa niewiele dłużej niż jednokrotne wyszukiwanie w pliku przypadku pesymistycznym. Wyszukiwanie w pliku zaś musi być liniowe jeżeli długość jednego elementu (linii) nie jest stała lub w inny sposób przewidywalna albo elementy nie są uporządkowane. Faktem jest, że trzymanie w pamięci całego, naprawdę sporego słownika to dosyć kiepski pomysł.
...nikt nie zauważył literówki w pierwszym poście - o trzymaniu w słoniku?
Witam. Czy mógłby ktoś użyczyć programu do sprawdzania gramatyki/ortogrfii w delphi?? Program powinien działać następująco:
W notatniku mamy taki mini słownik. Wpisujemy w naszym super programie jakiś tekst. Po napisaniu i wciśnięciu przycisku "sprawdź pisownie" komputer na zasadzie prawdopodobieństwa wypisze mi w jakimś oknie: W wyrazie "Który" prawdopodobnie popełniłeś błąd w trzeciej literze wyrazu ( może być coś podobnego). Wiadomo, że to jak mądry bedzie moj program uzależnione będzie od mojego zasobu słów w notatniku. Proszę was o pomoc, bo nie wiem jak sie za to zabrać. Musze to mieć na weekend gotowe. Z góry dziękuje. Pozdr
Coś kolo 1000 zł i będziesz mieć na weekend.
@_13th_Dragon przesadzasz troszkę bo takiego spellecheckera ostatnio na Przetwarzanie Języka Naturalnego i to jest max kilka godzin pisania ;)
@ziomek67 tutaj masz gotowca http://norvig.com/spell-correct.html w pythonie razem z artem który opisuje jak takie coś napisać.