Anagramacja (permutacja), scrabble i zapytanie MySQL Opcje

[altruista2]

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:

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

[Crozin]

Nie robiłem żadnych testów, ale wydaje mi się, że lepiej jest najpierw posortować alfabetycznie litery wyszukiwanego zwrotu:

Kod

Crozin -> cinorz (chyba dobrze to zrobiłem)

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.

[altruista2]

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

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

[altruista2]

Wielkie dzięki za pomoc!

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

[scrabblemania.pl]

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