Den kjappeste måten å finne anagrammer på?

[MetrOslo]

Hei,

Jeg har en MySQL-tabell med 267.751 ord. Jeg prøver finne den kjappeste måten å finne anagrammer på, uten å måtte lete gjennom hele tabellen for hvert søk, noe som ville vært utrolig ineffektivt. 

For ordensskyld: Et anagram er et ord som er blitt satt sammen ved å stokke rundt på bokstavene i et annet ord.

Jeg har kommet opp med en metode der jeg lager en ny kolonne, hvor bokstavene i alle ordene er sortert alfabetisk. Før jeg foretar et søk, sorterer jeg bokstavene i ordet alfabetisk, og søker i den nye kolonnen. Denne metoden viser seg å være mye kjappere. 

Metoden fungerer bra, men problemet er ikke å finne eksakte anagrammer (ord med samme antall bokstaver). Men å finne anagrammer du kan lage med en bokstav mindre, to bokstaver mindre, tre bokstaver mindre, og helt ned til 2 bokstaver. Det begynner plutselig å bli mange kombinasjoner.

Det er mange anagram-søkemotorer der ute, så dette burde ikke være vanskelig, men jeg klarer ikke å komme opp med en effektiv metode å gjøre det på. Er det noen som har noen ideer? Hvordan klarer de å gjøre det så kjapt?

Takk

 

Endret 23. juni 2021 av MetrOslo

[MailMan13]

Vil tippe de bruker en eller annen form for nummerisk frekvensmapping.

Sett at man f.eks bygger et frekvensmapping for hvert ord, så vil hvert anagram med færre bokstaver være et subset av det større ordet.

a = ABBA = { A: 2, B, 2 }
b = ABA = { A: 2, B, 1 }

a - b = { A: 0, B: 1 } => bare positive tall => b er sub-anagram av a
b - a = { A: 0, B: -1 } => oops, et negativt tall => a er ikke sub-anagram av b

Vanskelig å bygge inn i en lett traverserbar datastruktur da.

Men slike frekvensmappinger er hendige siden man kan representere dem rent nummerisk. Set at man tilordner hvert ord i alfabetet et unikt primtall.  For hvert ord tilordner man da tall likt produktet til tallene man har tilordnet. Ord som er anagrammer vil da ha et produkt av de samme primtallene og ha samme tallverdi. Ord som er subanagrammer vil alltid ha et produkt som er en faktor av produktet til ordet de er subanagram i.

A=2, B= 3, C=5, D=7.... 

ABBA => 2 * 3 * 3 * 2 = 36
BABA => 3 * 2 * 3 * 2 = 36 

ABBA - BABA = 0 => BABA har samme produkt => de er anagrammer

ABBA => 2 * 3 * 3 * 2 = 36
BAB => 3 * 2 * 3 = 18 

ABBA modulo BAB = 0 => BAB er faktor av ABBA => de er et sub-anagramm

En naiv implementasjon av dette vil måtte løpe gjennom hele listen for hvert ord, ihvertfall opp til b >= a/2, og gjøre en mod-operasjon. Det er ikke en veldig tung operasjon, man kan gjøre 200000 modulo på millisekunder i de fleste programmeringspråk. Så er det garantert masse triks som ramler ut av tallteorien rundt primtall som kan gjøre dette veldig mye mer effektivt enn det igjen...