Correspondance par rapport à la plus longue sous-chaîne

Question

Je cherche à renvoyer la meilleure correspondance d'une liste par rapport à une collection de listes.

x correspond à une liste de la collection si la liste de la collection de longueur n correspond aux n premiers éléments de x.

par exemple. [1,2,3] correspond à [1,2] mais [1,2] ne correspond pas à [1,2,3].

Je souhaite que la fonction renvoie la "meilleure" correspondance, c'est-à-dire la correspondance la plus longue.

par exemple.

bestMatch [1,2,3,3] [[1],[1,2,3],[1,2],[1,2,3,2],[1,2,3,4]] == Just [1,2,3] 

Il est évident que la liste n'est pas ici la meilleure structure de données, et je préfère utiliser une structure standard et la recherche plutôt que rouler mes propres idées, ce que je devrais utiliser et comment?

Je ne pense pas que les tables de hachage fonctionneront parce que les correspondances ne sont pas exactes. J'ai alors pensé à la recherche contre un arbre ordonné, mais il a le problème que si je recherche [1,2,100], j'obtiendrai [1,2,99], [1,2,98], ... etc avant d'obtenir la bonne réponse, [1,2]. Pourrait utiliser un hachage de hachages (et ainsi de suite dans l'arbre), mais cela semble être beaucoup de frais généraux.

(Une liste de recherche linéaire mise en œuvre est basée here)

Answer 1

A serait Trie une bonne solution. Dans votre cas, les valeurs seraient simplement (), indiquant qu'un nœud donné correspond à une fin de liste. Ensuite, si vous avez une liste, vous allez juste parcourir le trie le plus bas possible, et la dernière valeur rencontrée marquera la liste la plus longue.

A ByteString base Trie en Data.Trie offre match, qui semble être exactement ce que vous cherchez (si les clés seraient suffisantes pour vous CHARS 8 octets):

-- | Given a query, find the longest prefix with an associated value in 
-- the trie, returning that prefix, it's value, and the remaining string. 
match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString) 

Il y a aussi un autre paquet list-tries, qui a des clés plus génériques. Je ne suis pas sûr s'il y a une fonction exacte comme match ci-dessus, mais certainement il serait possible d'en implémenter un.