Mam problem jak w temacie: slownik zawiera wyrazy, powiedzmy ze
jeden
dwa
trzy
Przeszukujemy tekst w poszukiwaniu fragmentow CO NAJMNIEJ dwuliterowych. Wyszukane fragmenty trzeba pokolorowac. Na przyklad w tekscie
Jedna pani miala dwadziescia trzykolowych rowerkow
Bede wdzieczny za kazdy trop algorytmu.</b>
Slownik - okolo 1000 wyrazow.
W czym to ma byc? I co to za slownik? Plik txt czy co? I jak/w czym to chcesz pokolorowac? [glowa]
W czym to ma byc? I co to za slownik? Plik txt czy co? I jak/w czym to chcesz pokolorowac? [glowa]
W zasadzie jezyk dowolny, chociaz preferuje Delphi. Z kolorowaniem sobie poradze, bardziej mi chodzilo o zgrabny (czyli szybki) algorytm wyszukiwania fragmentow wyrazow - bo tworzenie n petli wydaje mi sie malo efektywne.
Forma slownika - dowolna, przy takiej ilosci slow mozna zalozyc ze siedzi juz w pamieci w jakiejs tablicy.
a ja mam pytanie - w slowniku bylo jeden, dwa, trzy, a dlazego masz zaznaczone jedna itp??
Poszukując pojedynczego wzorca, dosyć długiego przydatny byłby algorytm Rabin-Karpa, ale ponieważ nie są to raczej długie wyrazy (przynajmniej tak z opisu wynika), a jest ich dosyć dużo, to może zbudowanie DAS (lub NAS) dla tych wyrazów byłoby całkiem efektywną metodą przeszukiwania. Chociaż... skoro słownik zawiera 1000 wyrazów to trochę dużo. Powiedz może jeszcze ile znaków zawiera przeszukiwany tekst. To często też ma znaczenie. Z doświadczenia wiem, że dla małej ilości danych stosowanie skomplikowanych algorytmów wyszukiwania nie jest zbyt optymalne. Przepisane brute-force w asm zwykle bije je mocno dla mniejszej ilości danych.
a ja mam pytanie - w slowniku bylo jeden, dwa, trzy, a dlazego masz zaznaczone jedna itp??
Bo algorytm ma wyszukiwac podciagi, co najmniej dwuliterowe, czyli je, jed, jede, jeden :)
Poszukując pojedynczego wzorca, dosyć długiego przydatny byłby algorytm Rabin-Karpa, ale ponieważ nie są to raczej długie wyrazy (przynajmniej tak z opisu wynika), a jest ich dosyć dużo, to może zbudowanie DAS (lub NAS) dla tych wyrazów byłoby całkiem efektywną metodą przeszukiwania. Chociaż... skoro słownik zawiera 1000 wyrazów to trochę dużo. Powiedz może jeszcze ile znaków zawiera przeszukiwany tekst. To często też ma znaczenie. Z doświadczenia wiem, że dla małej ilości danych stosowanie skomplikowanych algorytmów wyszukiwania nie jest zbyt optymalne. Przepisane brute-force w asm zwykle bije je mocno dla mniejszej ilości danych.
OK, juz wyjasniam w czym problem:
Ogladam strone www. Nie przekracza z reguly jednego ekranu, powiedzmy ze srednio 1.5 screena. Wyrazy - zwykle, jak to w tekscie pisanym. Chce wyszukac optycznie miejsca, w ktorych moga sie pojawic numery GG - a pomyslowosc ludzi jest niewyobrazalna :) Potrafia napisac po angielsku, francusku, niemiecku, potrafia napisac "jedwtrczpisz" albo wspak.
Oczywiscie podkolorowanie fragmentow wyrazow jak w przykladzie - ulatwiloby mi kontrole.
Coz, wydaje mi sie, ze troszke zmodyfikowany brute-force tutaj wystarczy.
Po prostu przechodzisz caly tekst do przeszukania przesuwajac sie o 1 znak, ale odczytujac 2 na raz i porownujac te 2 z kazdymi dwoma znakami z listy tych 1000. Jezeli okaze sie, ze sie zgadza, to mozesz dalej juz zrobic porownanie dokladzniejsze. Caly podejrzewany wyraz. Jezeli nie, to przesuwasz sie o 1 znak i dalej odczytujesz. Porownujac, potraktuj te 2 znaki, jako 1 liczbe 16-bitowa.
Czyli bardziej schematycznie: