Cerca una sottostringa in un determinato array di stringhe

Naviga le tue risposte
1

Ho una matrice di n stringhe. Voglio selezionare tutti gli elementi dell'array che inizia con la stringa specificata.

Scusa se non è chiaro. Darò un esempio. 

input = "as"
array = ["abas", "aras", "as", "ask", "asi", "aso", "atas" ]
output =            ["as", "ask", "asi", "aso"]

Quale algoritmo dovrò fare questa selezione. Ho bisogno dell'algoritmo più veloce che eseguirà questa operazione dal momento che la sto usando per il completamento automatico in JavaScript. Quindi la ricerca dovrebbe essere più veloce della velocità di digitazione dell'utente.

Modifica : pensavo solo ai dati che devo pre-elaborare se utilizzo una struttura dati. I dati sarebbero dinamici, e devo eseguire un'operazione di inserimento che molte volte. Sto recuperando i dati in modo dinamico utilizzando le richieste AJAX.

Modifica 2 : la matrice potrebbe contenere 1 milione di voci e la ricerca dovrebbe essere effettuata in due punti. Uno sul lato server, per selezionare tutti gli elementi che corrispondono alla condizione. Questo può essere limitato a 10000 voci e l'altro sul lato client ... le dimensioni di ricerca saranno quelle 10000, e questo può essere limitato alle prime 250 voci.

Ci scusiamo per la modifica in ritardo della domanda.

    
posta Boopathi Rajaa 22.06.2011 - 12:56
fonte

3 risposte

5

Come fase di pre-elaborazione, trasforma la tua lista in trie .

a trie, also called digital tree or prefix tree, is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest...

The term trie comes from re-trie-val...

http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/250px-Trie_example.svg.png

    
risposta data 22.06.2011 - 13:07
fonte
1

È decisamente meglio usare uno degli algoritmi di completamento automatico già disponibili, ma se vuoi scrivere il tuo, un trie è la struttura dati ideale. L'inserimento e la ricerca avvengono entrambi in un tempo costante, cioè O (1), quindi la velocità non dovrebbe essere un problema.

Inoltre, questo sembra simile a quello che vuoi: link

    
risposta data 22.06.2011 - 13:29
fonte
0

Quanto è grande l'insieme di parole che vuoi cercare?

Per i piccoli set potrebbe essere meglio ordinare semplicemente il tuo array e quindi eseguire una ricerca binaria modificata per trovare il primo e l'ultimo elemento corrispondente.

Per i set più grandi probabilmente vorrai abbandonare del tutto l'array e andare per un trie.

Modifica
Dato che hai aggiornato per dire che ti stai aspettando un milione di parole ( in realtà, un milione di parole? Ci sono solo 171.476 parole nell'Oxford Dizionario inglese ) quindi un Trie è la soluzione migliore. Prima di implementare la tua implementazione, prenderei seriamente in considerazione alcuni degli strumenti di autocomplete disponibili gratuitamente.

    
risposta data 22.06.2011 - 13:07
fonte

Leggi altre domande sui tag

Come aumentare la velocità di caricamento della pagina in ASP.NET? [chiuso] Come devo comunicare le specifiche del cloud computing (rispetto ad altre)