Limitazioni e alternative ai tentativi in ​​lingue diverse dall'inglese?

Question

La struttura dati trie è spesso un ottimo modo per archiviare stringhe in inglese. Funziona costruendo un albero in cui ogni spigolo è etichettato con una lettera e il percorso di un nodo marcato nell'albero indica una delle parole nella struttura dati.

Questa struttura dati funziona bene in inglese perché ci sono "solo" 26 lettere dell'alfabeto inglese (un fattore di ramificazione "ragionevole"), quei caratteri hanno valori ASCII consecutivi (quindi i puntatori figlio possono essere memorizzati in un array con chiave dall'indice delle lettere usate da ogni bambino), e ci sono molte parole inglesi con prefissi comuni (quindi c'è molta ridondanza nella struttura).

Sono un madrelingua inglese con una conoscenza limitata solo di altre lingue e alfabeti, ma sembra che molte di queste proprietà non siano disponibili in altre lingue. So che francese, spagnolo, tedesco e ungherese, ad esempio, usano spesso caratteri accentati che non vengono memorizzati continuamente con le lettere rimanenti nello spazio Unicode. L'ebraico e l'arabo hanno segni vocalici che di solito sono indicati sopra o sotto ogni lettera. Il cinese utilizza un sistema logogramma e i caratteri Hangul coreani sono composti da tripli di caratteri più piccoli raggruppati insieme.

Le prove funzionano ancora bene per i dati memorizzati in queste lingue e alfabeti? Quali modifiche sono necessarie per utilizzare i tentativi per questo tipo di dati? Ci sono strutture dati che funzionano bene per le stringhe in quelle lingue e alfabeti che sono particolarmente adatti a loro ma che non sarebbero utili o efficienti in inglese?

Answer 1

Come addendum alla risposta di @ JimMischel, vorrei sollevare il problema che in altre lingue ci sono spesso più modi equivalenti per scrivere la stessa cosa. Vietnamese (basato sullo script latino/inglese) è un esempio particolarmente valido in cui le lettere con due accenti sono comuni. Ad esempio, Ặ (U + 1EB6) può essere tecnicamente anche con le sequenze Ă + punto, Ạ + breve, A + breve + punto, A + punto + breve.

Unicode normalization può risolvere questo problema convertendo una stringa in un ordine canonico standardizzato. Esistono 4 diverse varianti, NFC, NFKC, NFD e NFKD. Non entrerò troppo nel dettaglio qui, ma i primi due sono "forme composte" che tendono ad accorciare la stringa, raggruppando i caratteri di base con i suoi accenti, mentre gli ultimi due sono "forme scomposte", facendo l'opposto.

Hangul è un caso interessante: è un alfabeto, anche se tutte le lettere di una sillaba sono scritte insieme in un blocco. Sia le singole lettere che i blocchi sillabici esistono in Unicode. La normalizzazione può risolverlo, sebbene il numero di sillabe distinte sia piuttosto ampio. L'uso di NFC/NFKC potrebbe non essere utile per un trie, ma in questo caso, utilizzare NFD/NFKD per scomporre le sillabe nelle lettere costituenti potrebbe funzionare.

alcuni altri punti non collegati da considerare:

• Oltre al punto garçon/garcon già cresciuto, si ha la cote/coté/Costa/problema côté, che sono tutti distinti parole francesi. Allo stesso modo, i segni vocalici in ebraico e in arabo non sono solitamente obbligatori, il che può occasionalmente causare ambiguità.
• Gli alfabeti del Sud e Sud-Est asiatico possono diventare grandi rispetto all'inglese, circa il doppio delle dimensioni.

---

1. Essi sono rigorosamente denominato abugidas, in cui le vocali sono scritti come diacritici/accenti, ma questa distinzione di solito può essere ignorato da un punto di vista della programmazione.

Answer 2

Ho trovato che cerca di funzionare bene per le lingue dell'Europa occidentale, così come per il cirillico e molte altre lingue alfabetiche. Vieni a pensarci, le uniche lingue con cui ho avuto problemi erano cinesi, giapponesi e altri sistemi di scrittura logografica. E per quelli, il trie era inutile.

I valori Unicode sequenziali dei caratteri inglesi non rappresentano un vantaggio enorme. Sebbene suggerisce la semplice implementazione nodo:

CharNode 
    char 
    array[26] of CharNode 

Tale struttura non è particolarmente utile. Può rendere le cose più veloci, ma con un costo di memoria abbastanza alto. Anche al secondo livello di un trie, quell'array è notevolmente scarso. Quando arrivi al quarto o al quinto livello, è quasi tutto spazio morto. Ne ho fatto un'analisi a un certo punto. Mi guarderò intorno e vedrò se ho ancora i numeri.

Ho trovato quasi veloce avere un array a lunghezza variabile nel nodo, con elementi ordinati per frequenza. Oltre il secondo o terzo livello del trie, il personaggio che stavo cercando era quasi sempre nella prima o nella seconda posizione di quell'array. E il risparmio di spazio era abbastanza grande. Invece di 26 riferimenti per nodo (104 byte nella mia implementazione), avevo un conteggio di un byte e quindi cinque byte per riferimento. Quindi, fintanto che c'erano meno di 21 figli per un particolare nodo (che era la maggior parte delle volte), ho risparmiato spazio. C'era una piccola penalità di runtime, ma non abbastanza nella mia applicazione per importare.

Questa è l'unica modifica che ho dovuto apportare alla mia struttura per supportare tutte le lingue alfabetiche con cui stavo lavorando. Come ho detto, stavo lavorando principalmente con le lingue dell'Europa occidentale, e per quelli ha funzionato magnificamente. So che ha funzionato con l'ebraico e l'arabo, ma non so come funziona . Ha soddisfatto i nostri scopi, ma se sarebbe stato soddisfatto un madrelingua è sconosciuto.

Il trie I costruito ha funzionato abbastanza bene per i nostri scopi con qualsiasi linguaggio i cui caratteri si adattino al piano multilingue multilingue di Unicode. C'era un po 'di stranezza quando si lavorava con coppie surrogate, ma abbiamo praticamente ignorato quelle.Fondamentalmente, abbiamo trattato la coppia surrogata come due personaggi e lasciamolo andare.

È necessario decidere se si desidera trattare i caratteri accentati come caratteri separati o se si desidera mapparli. Si consideri, ad esempio, la parola francese "garçon", che alcune persone scriveranno "garcon", o perché non sanno fare meglio o non sanno come rendere il carattere "ç". A seconda di cosa stai usando il trie, potresti trovare utile convertire i caratteri accentati nei loro equivalenti non accentati. Ma suppongo che sia più un problema di pulizia degli input che un problema trie.

Questo è il mio modo abbastanza prolisso di dire che un trie standard dovrebbe funzionare bene per qualsiasi lingua alfabetica, senza modifiche specifiche della lingua. Non vedo alcun modo ovvio di usare un trie per un linguaggio logografico. Non so nulla di Hangul coreano, quindi non posso dire se un trie sarebbe stato utile lì.