Le Plus Efficace Algorithme pour Trouver d'Abord le Préfixe-Match à Partir d'une Triés Tableau de Chaîne?

D'entrée:

1) Un grand tableau trié de SA chaîne;

2) Un préfixe P;

De sortie:

L'indice de la première chaîne de caractères correspondant à l'entrée du préfixe si tout.
Si il n'y a pas de match, alors la sortie sera -1.

Exemple:
SA = {"ab", "abd", "fdea", "abz"}
P = "abd"
La sortie doit être de 1 (index à partir de 0).

Quel est le meilleur algorithme de façon à faire ce genre de travail?

OriginalL'auteur Morgan Cheng | 2009-01-19

  1. 19

    Si vous ne voulez faire qu'une seule fois, utilisez recherche binaire, si d'autre part vous avez besoin de le faire pour de nombreux préfixes différents, mais sur le même tableau de chaîne, la construction d'un radix arbre peut être une bonne idée, après que vous avez construit l'arbre chaque look jusqu'sera très rapide.

    Dans le meilleur des cas recherche du temps pour la base de l'arbre est O(n) où n est le nombre de caractères, tandis que la recherche binaire prend O(log m) où m est la taille de la liste. Ce n'est pas necessarially vrai que radix recherche sera plus rapide.
    Arachnides: Ce n'est pas vrai. Même dans le meilleur des cas (où il y a un match), binaire de recherche est O(n + log m), car il doit lire l'ensemble de préfixe pour vérifier si elle correspond. Dans le pire des cas est O(nlogm).
    pour les de Brian de commentaires, plus O(n) est le PIRE des cas recherche pour base de l'arbre, où il y a un match et vous avez besoin de lire tout le préfixe.
    Ainsi, une recherche binaire est presque trivial à mettre en œuvre, et ne prend pas de mémoire supplémentaire. Radix les arbres sont compliquées à mettre en œuvre, de prendre plus de mémoire, et l'intérêt n'est pas énorme
    _.sortedIndex rend encore plus triviale 🙂

    OriginalL'auteur Joe Lindström

  2. 3

    Il peut être fait en temps linéaire à l'aide d'un Le Suffixe De L'Arbre. La construction du suffixe arbre prend le temps linéaire.

    Il pourrait comparer le préfixe de chaque élément dans le temps linéaire.
    Vrai, mais si il va vérifier plus d'un préfixe, ce n'est pas une bonne idée.

    OriginalL'auteur Brian

  3. 2

    C'est juste une modification de la bissection de recherche:

    • Seulement de vérifier que le nombre de caractères dans chaque élément que sont la chaîne de recherche; et
    • Si vous trouvez une correspondance, de poursuivre la recherche vers l'arrière (de façon linéaire ou par d'autres non-bloquante de recherche) jusqu'à ce que vous trouver une non-correspondance de résultat et puis retour à l'index de la dernière règle de résultat.

    OriginalL'auteur cletus

  4. 0

    Le noyau de FreeBSD utiliser un Radix arbre pour sa table de routage, vous devez vérifier que.

    OriginalL'auteur Keltia

  5. 0

    Ma solution actuelle à l'esprit est, au lieu de trouver le "préfixe", essayez de trouver un "virtuel préfixe".

    Par exemple, le préfixe est “abd", essayez de trouver un virtuel-le préfixe “abc(255)". (255) représente le nombre de caractères max. Après avoir trouvé le "abc(255)". Le mot suivant doit être le premier mot correspondant "abd" si tout.

    OriginalL'auteur Morgan Cheng

  6. 0

    Êtes-vous dans la position de précalculer possible préfixes?

    Si oui, vous pouvez le faire, puis d'utiliser un binaire de recherche pour trouver le préfixe de la table précalculée. Magasin de l'indice à la valeur souhaitée avec le préfixe.

    OriginalL'auteur EvilTeach