Algoritmo per la compressione di un dizionario (parole e definizioni)

Question

Algoritmo per la compressione di un dizionario (parole e definizioni)

#1 da (1 voti)

0

La situazione teorica è questa:

Diciamo che abbiamo un dizionario digitale (con cui intendo un elenco tradizionale di parole e definizioni, non un array associativo). Per semplicità, diciamo anche che ogni parola può essere sostituita dalla sua esatta definizione, e ha ancora senso in una frase; per esempio, se questo dizionario contiene la definizione della parola "oceano" per essere "grande corpo di acqua salata", quindi il seguente passaggio:

"We ourselves feel that what we are doing is just a drop in the ocean."

potrebbe essere modificato in:

"We ourselves feel that what we are doing is just a drop in the large body of salt water."

senza alcuna perdita di logica o significato. Ora la mia domanda è questa: dato un dizionario con tutte le parole in inglese, qual è un algoritmo che potrebbe essere applicato per comprimere il dizionario, attraverso la sostituzione di tutte le occorrenze di una determinata parola con la sua definizione, e nel fare quindi trovare un insieme di parole base attraverso cui poter esprimere tutti i significati della lingua originale?

Per chiarire ancora di più; se "tristezza" è definita come "un'emozione infelice", allora la parola tristezza può essere completamente rimossa dal dizionario sostituendo tutte le occorrenze della parola "tristezza" che si verificano nelle definizioni di altre parole con la sua definizione. La definizione di "depressione", ad esempio, potrebbe cambiare da "un periodo prolungato di tristezza" a "un periodo prolungato di un'emozione infelice". In questo modo, l'algoritmo alla fine arriverebbe a un insieme di parole base da cui potrebbero essere rappresentate tutte le altre parole.

Esistono degli algoritmi che possono farlo o qualcosa di simile? Come potrebbe essere fatto a livello di codice, senza usare la forza bruta? Qualsiasi comprensione è apprezzata.

algorithms dictionary compression

posta ANortonsmith 07.09.2013 - 04:30

fonte

1 risposta

Leggi altre domande sui tag algorithms dictionary compression

Scrape sito Intranet senza un server web aiuto in teoria riguardo a prefix_suffix_set

score 1 · Accepted Answer

Puoi modellare questo è un grafico diretto. Ogni vertice nel grafico rappresenta una parola, un bordo in uscita rappresenta le parole utilizzate per definire la parola e un bordo in entrata rappresenta altre parole che utilizzano questa parola nella loro definizione.

È possibile eliminare vertici non ricorsivi connettendo i vertici dai bordi in entrata ai vertici nei bordi in uscita. In pseudocode:

all_words = ...
current = select_node_to_eliminate(all_words)
for n1 in current.incoming_edges:
    for n2 in current.outgoing_edges:
        if n1 != n2:
            add_edge(n1, n2)
            remove_edge(n1, current)
            remove_edge(current, n2)
if len(current.incoming_edges) == 0 and len(current.outoing_edges) == 0:
    all_words.remove(current)

Il problema è che il risultato finale di "un insieme di parole base da cui potrebbero essere rappresentate tutte le altre parole" dipenderà molto da come scrivi select_node_to_eliminate() .

Dovresti definire criteri aggiuntivi per "dizionario minimale". Vuoi il dizionario più piccolo come nel più piccolo numero di parole, anche a costo di definizioni lunghe e incomprensibili; o si desidera includere la dimensione delle definizioni quando si calcola la dimensione del dizionario.