Anagramacja (permutacja), scrabble i zapytanie MySQL Opcje

[altruista2]

Na początek chciałbym przywitać wszystkich, jestem tu nowy (IMG:style_emoticons/default/smile.gif)

Oto problem:

Tworzę stronę o scrabble i chcę zrobić narzędzie anagramator takie jak tu:
http://www.pfs.org.pl/anagramator.php
Chcę osiągnąć jak największą wydajność przy anagramacji i nie potrafię wymyślić dobrej struktury tabeli MySQL ze słówkami jak i samego zapytania. (W bazie znajduje się >1.000.000 słów)

Jedyna rozwiązanie na jakie wpadłem to takie, że tabela składa się ze słowa i 26 kolumn odpowiadającym ilości danej litery w słowie oraz jedej kolumna odpowiadająca ilościom liter w słowie - czyli np. [b]TRAMWAJ[b] to:

T - 1
R - 1
A - 2
M - 1
W - 1
J - 1
Długość - 7

zapytanie SQL wygląda tak:

Kod

SELECT Słowo FROM Tabela WHERE T=1 AND R=1 AND A=2 AND M=1 AND W=1 AND J=1 AND Dlugosc=7

Niestety takie zapytanie zajmuje ok. 2-3 sekundy, co jest kompletnie niewydajne.
Próbowałem też z RLIKE, REGEXP itd. ale to wychodzi jeszcze gorzej...

Czy ma ktoś "szybszy" pomysł? (IMG:style_emoticons/default/smile.gif) )

[Aztech]

Proponuję zapoznanie się z pracą Daniela Janusa na temat systemu Pliquarp, który służy do wyszukiwania słów w Korpusie języka Polskiego (używanego w PWN), no i przede wszystkim polecam przeczytanie książki Knutha o generowaniu wszystkich krotek i permutacji.
Po tej lekturze na pewno przyjdzie Ci jakieś rozwiązanie do głowy (IMG:style_emoticons/default/biggrin.gif) .
Co możesz zrobić (ja tak zrobiłem w swoim programie działającym a'la OSPS/Anagramator to:
I1) stworzyć dodatkową indeksowaną kolumnę zawierającą informację o długości słowa
I2) stworzyć dodatkową indeksowaną kolumnę zawierająca pierwszą literę wyrazu
I3) stworzyć dodatkową kolumnę zawierającą wszystkie litery z wyrazu posortowane od A do Z
Zadawanie zapytania do bazy wyglądałoby następująco:
Z1) Bierzesz wszystkie litery (bez blanków) i tworzysz z nich wszystkie permutacje
Z2) Bierzesz blanki podstawiasz po kolei literki A-Z, tworząc permutacje
Z3) Robisz permutacje obu tych zbiorów, a następnie usuwasz duplikaty, sortujesz litery od A-Z
Z4) Przesyłasz zapytanie do bazy, korzystając z indeksów: I1 oraz I3

Mój programik, napisany w podobny, do powyższego algorytmu, sposób generuje losowo 100 słów 7 literowych a następnie przeszukuje całą bazę, czy nie ma w nim przypadkiem innych słów z tych samych liter. Cały proces, PHP + baza MySQL (MyISAM) + framework PRADO wykonują to zadanie (bez żadnych cache'ów i akceleratorów) w ok 1,5 minuty (1 słowo wraz z permutacjami ok 0,5 sek).

P.S. Proponuję również zapoznać się z tym wątkiem
P.S.2. Aby zoptymalizować twoje zapytanie, dodaj indeks do kolumn z ilością wystąpień danej litery
P.S.3 Aha, jest jeszcze algorytm Knutja-Morrisa-Pratta

Ten post edytował Aztech 11.02.2010, 10:42:25