Ave.
Niby jaką?
Niezbyt miłe.
No dobra, mniejsza z tym. W każdym razie tak:
Algorytm naiwny faktycznie niezbyt wesoły jeśli słów chcesz mieć dużo (setki tysięcy? Tyle chyba w języku polskim nie ma :( ) i robić dużo (tysiące?) zapytań na raz.
Nie szukaj jak go przyśpieszyć, bo nic nie znajdziesz ciekawego. Ma złożoność pesymistyczną = optymistyczną = O(n * m) (n = liczba napisów, m = długość wzorca) - jeśli musisz przejrzeć wszystkie napisy w tekście, nie ma szans żeby to bardzo szybko działało.
Propozycja bardziej algorytmicznych podejść do sprawy (wymaga zmiany struktury danych):
Pierwszym pomysłem przychodzącym do głowy jest trie.
Nie jest tak trudne do implementacji, przy dobrze napisanym będzie bardzo szybkie dla typowego przypadku. Niestety, w pesymistycznym nie będzie tak różowo.
Konkretnie, złożoność to O(min(z + c^n, m)) - gdzie z to liczba znanych znaków we wzorcu, n to liczba nieznanych znaków we wzorcu (wildcardów), c to rozmiar alfabetu a m to łączna liczba słów (wiem, pełno tych oznaczeń) - to znaczy, złożoność rośnie wykładniczo z ilością niewiadomych znaków w napisie, ale na szczęście nigdy nie przekracza ilości słów łącznie.
O co dokładniej chodzi w tym sposobie. Trie to taka sprytna struktura danych, co służy właśnie do wygodnego przechowywania i odpytywania zbiorów napisów.
Wygląda ono tak, że idąc od korzenia przechodząc przez kolejne węzły
drzewa odtwarzamy dodane napisy. Na przykład że jeśli są napisy ALA, ALAMAKOTA, ANANAS, ANARCHIA, ANARCHISTA i BATMAN, powstanie drzewo:
*
/
L-A
/ \
A M-A-K-O-T-A-*
/ \
/ N-A-N-A-S-*
/ \
* A-R-C-H-I-A-*
\ \
\ S-T-A-*
\
B-A-T-M-A-N-*
Jak takiego drzewa użyć do znalezienia wszystkich pasujących (to nie ma byc działający kod, tylko formalny pseudokod. Ale z niewielkimi modyfikacjami, i oczywiście tworzeniem drzewa, powinno zadziałać bez problemów):
struct trie_t {
trie **child[CHARSET_SIZE];
// może jeszcze ew. parent do otworzenia słowa.
};
void find_all(trie_t *root, char *left) {
if (*left == '#') { // jeśli kolejny znak we wzorcu to wildcard
for (int i = 'a'; i < 'z'; i++) { // sprawdzenie wszystkich możliwych gałęzi trie wychodzących z tego punktu
// uściślenie - zamiast testować wszystko 'a'-'z' dobrym pomysłem jest trzymanie listy niezerowych gałęzi wychodzących. Nie zrobiłem tego od razu, bo komplikowałoby pseudokod niepotrzebnie a pomysł ten sam.
if (root.child[i] != 0) { // oczywiście nie można sprawdzać w tablicy po prostu 'a', 'b' itd - trzeba je zamieniać na 1, 2, 3 itp
find_all(root.child[i], left + 1); // i rekurencyjne szukanie w nich - stąd ta wykładnicza złożoność
}
}
} else {
if (root.child[*left] != 0) { // jeśli obecny węzeł zawiera kolejny znak z wzorca, sprawdzamy czy doprowadzi nas do końca
if (*left != '\0') { // jeśli kolejny znak nie jest nulem (to nie koniec napisu)
find_all(root.child[*left], left + 1); // idziemy wgłąb drzewa sprawdzając dalej.
} else { // jeśli to nul, znaleźliśmy.
printf("Znaleziono"); // i tu by wypadało odtworzyć słowo idąc w górę czy coś...
}
}
}
}
Nie wiem czy jasno to wytłumaczyłem, więc przykład na poprzednim drzewie - szukamy A#ANAS:
*
/
L-A
/ \
A M-A-K-O-T-A-*
/ \
/ N-A-N-A-S-*
/ \
* A-R-C-H-I-A-*
\ \
\ S-T-A-*
\
B-A-T-M-A-N-*
Na początku wzorca znak A - wchodzimy w górne
poddrzewo z literą A. Następnie jest wildcard, więc wchodzimy rekurencyjnie we wszystkie poddrzewa. W każdym z poddrzew próbujemy dopasować ANAS
, i tak algorytm idzie aż znajdzie wszystkie dopasowania.
To tyle o trie, jeśli będzie Ci się chciało je zaimplementować to będzie prawdopodobnie w realistycznych przypadkach działać bardzo szybko (poza napisami w stylu ####A####, ale to patologia).
Jest też alternatywny algorytm który mógłby być szybszy, ale nie mam na tyle odwagi żeby o drugiej w nocy przeprowadzać analizę jego złożoności ;]. Pomysł opiera się na tym, żeby dla każdego zbioru słów o długości n (słowa różniące się długością z wzorcem i tak nie mogą być dopasowane) trzymać listę zbiorów słów mających tą literę na tym miejscu. Hmm, nic nie wynika z poprzedniego zdania. Tzn. jeśli mamy słowa ABA, GAA, BBB, powstaje struktura:
/A : ABA
/-B : BBB
[_]--G : GGG
/A : GAA
[_]-B : ABA, BBB
/A : GAA, ABA
[_]-B : BBB
I teraz szukanie wzorca polega na łączeniu zbiorów - czyli jeśli mamy A#A, to wykonujemy:
zbiór napisów mających A na pierwszym miejscu = { ABA }
drugi znak pomijamy
zbiór napisów mających A na ostatnim miejscu = { GAA, ABA }
i bierzemy część wspólną zbiorów: { ABA } /\ { GAA, ABA } = { ABA }
Wąskim gardłem jest część wspólna zbiorów. Nie jestem pewien jak bym to rozwiązał, ale istnieją szybkie algorytmy części wspólnej z n zbiorów... No i są bloom filtery, które tutaj można by zastosować ;]