Szukanie substringów

Mam słowo, np. euroautointegrator i teraz chcę to rozdzielić tak: euro-auto-integrator,
czyli na te słowa, z których to złożono.

Słowa często występujące w złożeniach mam przygotowane i jest ich kilkaset lub nawet kilka tysięcy:
'auto', 'trans', 'zielono', 'mało', 'szkolno'

Sprawdzanie kolejno wszystkich:

for i := 1 to Num do begin
   k := Pos(zlozone, slowka[i]
   if k > 0 then begin 
      
       znaleziono...

   end
end;

jest zbyt wolne, więc szukam lepszego sposobu - hash table lub coś w tym stylu.

Może ma ktoś jakiś pomysł?

pastelowogruboziarnistoszybkoskośnie

ja bym to walnal na drzewo ;-) kazdy wierzcholek ma tylu synow ile jest liter w alfabecie. Wczytujesz literke i schodzisz poziom nizej i tak az do momentu az nie bedzie znacznika ze jest cale slowo, wtedy je wypisujesz robisz myslnik i od nowa :-)

az do EOF

edit: zlozonosc liniowa wzgledem ilosci liter

lmmilewski napisał(a)

kazdy wierzcholek ma tylu synow ile jest liter w alfabecie.

Złożoność czasowa prawie liniowa, ale wykładnicze zapotrzebowanie na pamięć:
każdy węzeł ma 35-ciu synków, czyli dla słów długości do 10 literek będzie:
35^10 = 2758547353515625 węzłów, nie stać mnie na tyle RAM-u. :-)

Odpowiedzią jest tak zwane drzewko trie (zwane również prefiksowym). W sumie chyba to miał na myśli mniej-więcej Immilewski. Każdym węzłem drzewka jest litera, powiedzmy, że #0 oznacza koniec wyrazu. I teraz przeszukując DFS'em takie drzewo od korzenia, otrzymasz wszystkie przechowywane tam wyrazy. Natomiast idąć po ścieżce, wyznaczonej przez wyraz (po kolejnych literach w dół drzewa), aż do #0 (i od nowa...), uzyskasz szukany podział. Problem może się pojawić, gdy będziesz miał np. takie słowa w słowniku: "auto", "automat", "matematyk", "kot". Wtedy musiałbyś sprawdzić wszystkie możliwe rozkłady, aż do uzyskania kompletnego, co trochę obniżyłoby wydajność i skomplikowało implementację. (przykładowe słowa sypiące się na opisanym wyżej algo: automatkot, automatematyk (heurestyki by tu nie działały)).

Złożoność:

• tworzenie drzewka: O(n) //n - suma długości słów do słownika
• wyszukanie podziału O(m) //m - długość słowa

Pawel200x.5 napisał(a)

Problem może się pojawić, gdy będziesz miał np. takie słowa w słowniku: "auto", "automat", "matematyk", "kot". Wtedy musiałbyś sprawdzić wszystkie możliwe rozkłady, aż do uzyskania kompletnego, co trochę obniżyłoby wydajność i skomplikowało implementację. (przykładowe słowa sypiące się na opisanym wyżej algo: automatkot, automatematyk (heurestyki by tu nie działały)).

Słowa częściowo pokrywające się nie przeszkadzają - szukam najdłuższe dopasowanie i już:

nie podzieli się auto-matkot, bo matkot nie będzie w słowniku,
'auto' znajdzie, ale dłuższe jest 'automat' i plus 'kot' daje 100% więc będzie ok.

automat-ematyk też odpadnie - auto+matematyk wygra z automat - 'ematyk' raczej nie będzie w słowniku.

Te drzewa to chyba nie jest najlepsze rozwiązanie - aby coś znaleźć trzeba przejść
po węzłach aż do liścia, a w tablicy hash wystarcza jeden strzał, ale kolizje psują trochę sprawę...

Drzewa trie na pewno są lepszym rozwiązaniem. Złożoność przy hashtabie jest co najmniej taka sama (raczej gorsza), a na dodatek w trie łatwiej wyszukać najdłuższe podsłowo.
Na hashtabie, przy automatematyk musiałbyś najpierw sprawdzic 'a', potem 'au', potem 'aut'... i dla każdego z nich liczyć hash, więc gdyby (H - funkcja hashująca, w - wyraz, c - znak) H(w+c) != f(H(w), c) (dla każdego w i c), to złożoność rośnie Ci aż do O(n^2). Na dodatek, przy tym wyszukiwanie 'całkowitego podziału' (dopasowywanie ciągle najdłuższych to zła heurystyka, trzeba sprawdzić wiele możliwości, DFS'em) jest dużo bardziej czasochłonne.

Z tym hashtable jest trochę inaczej - jest algorytm Rabina Karpowa, cykliczny hash plus kilka drobiazgów...
i nie będzie nigdy o(n^2),
ale te drzewa chyba lepiej tu spasują.

Jest tu jeszcze jeden problem - marnowanie pamięci może być znaczne,
najprościej gdy węzły będą wyglądać tak:

record Trie
 next : array[Alfabet] of PTrie;
 ostatnia_litera : Boolean;
end;

Mamy tu ponad 30 wskaźników, z których większość będzie nil czyli niepotrzebna.
Można zrobić tu jakąś listę zamiast tej tablicy, ale wtedy wszystkie zalety tego drzewa diabli wezmą -
aby sprawdzić literkę trzeba przejść po tej liście najczęściej aż do końca. :-(

Wybór listy czy tablicy statycznej zależy tylko od tego, czy bardziej zależy nam na oszczędzeniu czasu, czy pamięci. Co do hashtabów, to istotnie... Ja napisałem, że n^2 jest, gdy funkcja hashująca jest nieoptymalna pod tym względem. Przy liście i tak jest maksymalnie 30 elementów, więc spadek wydajności jest niewielki... Złożoność ta sama. Tak czy siak, osobiście sądze, że trie jest tutaj optymalnym rozwiązaniem :]