Meilleure structure de données pour la recherche de mots croisés puzzle

Question

J'ai une grande base de données pour résoudre des puzzles de mots croisés, composé d'un mot et une description. Mon application permet de rechercher des mots d'une longueur spécifique et des personnages sur des positions spécifiques (cela se fait à la dure ... passer par tous les mots et vérifier chacun). De plus une recherche par description (si nécessaire)

Par exemple trouver mot _ _ _ _ A B (6 mot de lettre, troisième et dernier caractère A B)

Je voudrais indexer les mots de telle sorte que la recherche serait vraiment rapide. Ma première idée était d'utiliser une structure arborescente équilibrée, toute autre suggestion?

Answer 1

D'accord, je vais proposer quelque chose de bizarre, mais venant de C++ J'utilise Boost depuis longtemps et je suis venu voir la bibliothèque MultiIndex.

L'idée de cette bibliothèque est de créer une collection, mais ont de nombreuses façons différentes pour l'interroger. Il pourrait modéliser, en fait, une base de données.

Alors, nous allons mettre nos mots dans une table, et de mettre les indices nécessaires en place:

word                     |length|c0|c1|c2| ... |c26|
-------------------------|------|--|--|--| ... |---|
Singapour                |9     |S |i |n | ... |0  |

Maintenant, la requête ressemblera à ceci:

Select word From table Where length=9 And c2='n' And c8='u';

Assez facile non?

Pour une efficacité maximale, la table doit être divisé sur la longueur, et les indices (un par colonne Cx) doit être local à la partition.

Pour une solution en mémoire que vous auriez un conteneur par longueur, contenant autant d'index que la longueur, chaque indice étant une table de hachage pointant vers une liste triée (fusion plus facile)

Voici une description de python:

class Dictionary:
  def __init__(self, length):
    self.length = length
    self.words = set([])
    self.indexes = collections.defaultdict(set)

  def add(self, word):
    if len(word) != self.length:
      raise RuntimeException(word + ' is not ' + `self.length` + ' characters long')

    if word in self.words:
      raise RuntimeException(word + ' is already in the dictionary')

    self.words.add(word)

    for i in range(0,length):
      self.indexes[(i,word[i])].add(word)

  def search(self, list):
    """list: list of tuples (position,character)
    """
    def compare(lhs,rhs): return cmp(len(lhs),len(rhs))

    sets = [self.indexes[elem] for elem in list]
    sets.sort(compare)
    return reduce(intersection, sets)

J'ai volontairement fourni l'argument length, afin de minimiser la taille des hash et ainsi faire la meilleure recherche. De plus, les jeux sont classés par longueur, de sorte que le calcul de l'intersection mieux:)

Allez-y et testez contre d'autres solutions si vous le souhaitez:)

Answer 2

Cette question: bon algorithme et structure de données pour rechercher des mots avec des lettres manquantes? a commencé exactement comme celui que vous demandez, mais il a été édité à quelque chose d'assez différent et plus facile. Pourtant, vous pouvez trouver quelques idées là-bas.

En bref, tout le monde recommande de charger le dictionnaire entier en mémoire et en divisant les mots en groupes en fonction de leur longueur. A partir de là, vous pouvez aller de nombreuses directions différentes. Plus de mémoire que vous êtes prêt à utiliser haut, plus vite vous pouvez aller.

Une bonne suggestion est de garder une table de hachage des listes de mots d'une longueur donnée qui ont une lettre donnée dans une position donnée. Vous pouvez construire comme ça (en Python):

# Build a whole lot of sorted word lists
wordlists = collections.defaultdict(list)
for word in sorted(all_words):
    for position, letter in enumerate(word):
        wordlists[len(word), position, letter].append(word)

Maintenant, si vous avez besoin d'un mot de 6 lettres se terminant par B, vous pouvez simplement demander wordlists[6, 5, 'B'] et vous avez la liste complète. Lorsque vous en savez plus d'une lettre, comme dans ..A..B, vous pouvez choisir selon la liste est la plus courte et tester chaque mot contre le motif désiré. Le dictionnaire de mon ordinateur a seulement 21 mots de six lettres se terminant par B, dont seulement les matchs SCARAB.

Answer 3

Puisque vous utilisez une base de données, créez une table Suffixes.
Par exemple:

  Suffix          |   WordID   | SN
  ----------------+------------+----   
  StackOverflow           10      1
  tackOverflow            10      2
  ackOverflow             10      3
  ckOverflow              10      4
  kOverflow               10      5
  ...

Avec cette table, il est facile d'obtenir tous les mots qui contiennent un omble particulier dans une position spécifique,
comme ceci:

SELECT WordID FROM suffixes
WHERE suffix >= 't' AND suffix < 'u' AND SN = 2

Obtenir tous les mots qui contiennent 't' à 2 position.

Mise à jour: si vous voulez économiser de l'espace, et sacrifier un peu de vitesse, vous pouvez utiliser un tableau de suffixe .

Vous pouvez stocker tous les mots dans une ligne (tableau) avec un séparateur d'entre eux, à savoir le $, et créer un tableau de suffixe qui ont des pointeurs vers des caractères. Maintenant, étant donné char c vous pouvez trouver toutes les occurrences de mots qui contiennent assez rapidement. Pourtant, vous devrez examiner si elle est dans la bonne position.
(En vérifiant dans quelle mesure il est des $s)

Probablement les ci-dessus technique la recherche sera x10 plus vite que la recherche de tous les mots dans votre programme original.

Mise à jour 2: Je l'ai utilisé l'approche de base de données dans l'un de mes utilitaires où je devais trouver suffixes tels que « ne », par exemple, et j'ai oublié de régler (Optimize) pour ce problème spécifique.

Vous pouvez simplement stocker un seul char comme suffixe:

  Suffix   |   WordID   | SN
  ---------+------------+----   
  S                10      1
  t                10      2
  a                10      3
  c                10      4
  k                10      5
  ...

qui permet d'économiser beaucoup d'espace. Maintenant, la requête devient

SELECT WordID FROM suffixes
WHERE suffix = 't' AND SN = 2

Answer 4

Vous pouvez utiliser un Suffixe Arbre , ou Trie.

Answer 5

Vous pouvez stocker vos informations dans une structure arborescente de quelque sorte (peut-être un arbre de recherche ternaire). Un algorithme de recherche partielle en utilisant une structure arborescente est décrit dans la section 6 de cet article par Sedgewick et Bentley. Vous voulez bien sûr d'avoir différents essais pour les différentes longueurs de mots. Le document dit que l'algorithme de recherche partielle nécessite un temps de O (n ^ ((k-s) / k)) pour les lettres de s étant précisé dans une structure arborescente de n mots k-longueur.