Struttura dati per attraversare nomi host gerarchici

Question

Struttura dati per attraversare nomi host gerarchici

#1 da (3 voti)

3

Quindi, molto spesso incontrerò una situazione in cui mi piacerebbe elaborare i nomi degli host in modo gerarchico.

Ad esempio, dato un nome host "foo.bar.baz.example.com", potrei volerlo confrontare con una struttura dati che contiene un'autorità più alta come "example.com" o "baz.example.com" e vedere se ottengo una corrispondenza.

Di solito, il modo in cui gestisco questo è semplicemente utilizzare un hashtable e rimuovere iterativamente i sottodomini fino a quando non trovo una corrispondenza (o, mai trovare una corrispondenza, qualunque sia il caso.)

Ma stavo pensando che qualcosa come un albero trie / prefix potrebbe essere molto più adatto per questo (se dovessi invertire le etichette dei domini).

Naturalmente, il problema è che un trie di solito lavora su singoli personaggi - mentre in questo caso vorrei fare in modo che ogni sottodominio (o "etichetta", in DNS-speak), una singola "unità".

Esiste una struttura dati che potrebbe essere adatta per qualcosa di simile?

data-structures trie

posta Siler 21.10.2014 - 18:50

fonte

1 risposta

Leggi altre domande sui tag data-structures trie

Perché 'JButton' è-un 'contenitore' in javax.swing? La sessione "fuoco amichevole" riproduce un problema valido?

score 3 · Answer 1

Usa un albero, in cui ogni nodo sarà un sottodominio. Il livello superiore sarà il simbolo di partenza. Quindi si diramerebbe in k nodi, dove k è il numero di domini di primo livello che hai.

Ad esempio, se l'intero database era costituito da due entità: foo.bar.example.com e boo.car.ample.net, k sarà 2 (net e com). Ciascuna rete e i nodi avranno un figlio ciascuno: ampio ed esempio. E così via.

Come altro esempio, consideriamo di avere di nuovo solo due entità. Ma questa volta è foo.bar.example.com e boo.bar.example.com. Ora l'albero sarebbe qualcosa di simile.

                                      root
                                       |       
                                      com
                                       |
                                    example
                                       |
                                      bar 
                                    /     \
                                  foo     boo

Questo sarà il tuo albero. Se l'input è example.com, divideresti per "." e invertire per ottenere [com, esempio]. Scenderai il tuo albero abbinando la lista all'albero. Dato che 'com' è figlio di root, tu prendi quel percorso, e da 'com', cerchi l'elemento successivo nella tua lista di input 'esempio'. Poiché "esempio" è un figlio di "com" nell'albero, procediamo. Ma ora abbiamo esaurito la lista di input e questo significa che abbiamo trovato una corrispondenza. In qualsiasi punto della traversa, se non trovi un bambino per l'elemento di input corrente dall'elenco, hai la certezza che non ci sono corrispondenze nel tuo database. Ad esempio se hai ottenuto la stringa di input zoo.bar.example.com. La nostra lista di input sarà [com, example, bar, zoo]. Avremmo attraversato l'albero fino al bar, ma nella "barra" dell'albero non c'è uno "zoo" per bambini. Ciò implica che non abbiamo zoo.bar.example.com nel nostro database.

Puoi trovare una corrispondenza in O (n), dove n è il numero di sottodomini nella stringa di input che stai cercando di trovare.