Na początek chciałbym przywitać wszystkich, jestem tu nowy

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:


zapytanie SQL wygląda tak:


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ł? )

Nie robiłem żadnych testów, ale wydaje mi się, że lepiej jest najpierw posortować alfabetycznie litery wyszukiwanego zwrotu:I wyszukiwać właśnie takiego zwrotu. Oczywiście w bazie danych musiałbyś mieć tabelę ze słowami, kolejną z posortowanymi literami słów oraz ostatnią łączącą obie.

Problem stanowią jedynie te blanki. Jednakże tutaj ograniczyłbyś się ponownie jedynie do wybrania odpowiednich ID z tabeli posegregowanych liter (no cholera zapomniałem jak się to normalnie nazywa ).

Później wystarczy już tylko wybrać listę słów, które są powiązane (tabela powiązań) z danymi posegregowanymi literami.

Też myślałem o tym, ale spójrz:

TRAMWAJ =
AAJMWRT

będę chciał zaanagramować AA*MWRT czyli AAMWRT i mi nie znajdzie:

AAJMWRT
AAMWRT

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 .
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

Wielkie dzięki za pomoc!

Patrząc na Twój awatar widzę że jesteś głęboko w temacie

mnie się udało osiągnąć całkiem przyzwoite wyniki na mssql wykorzystując zwykle indeksy.

tu można znaleźć gotowe rozwiązanie

scrabble słownik szukanie wyrazów

jeśli jest wystarczająca wydajność chętnie pokaże środek.


pozdrawiam

scrabblemania.pl