Una soluzione praticabile per la divisione di Khmer in Word?

Question

Sto lavorando a una soluzione per dividere le lunghe righe di Khmer (la lingua cambogiana) in singole parole (in UTF-8). Khmer non usa spazi tra le parole. Ci sono alcune soluzioni là fuori, ma sono tutt'altro che adeguate (here e here), e quei progetti sono caduti nel dimenticatoio.

Ecco una linea campione di Khmer che ha bisogno di essere diviso (possono essere più lungo di questo):

ចូរ សរសើរ ដល់ ទ្រង់ ដែល ទ្រង់ បាន ប្រទាន ការ ទាំងអស់ នោះ មកដល់ រូប អ្នក ដោយ ព្រោះ អង្គ ព្រះយេស៊ូវ ហើយ ដែល អ្នក មិនអាច រក ការ ទាំងអស់ នោះ ដោយសារ ការប្រព្រឹត្ត របស់ អ្នក ឡើយ.

L'obiettivo di creare una soluzione praticabile che divide le parole Khmer è duplice: essa incoraggerà quelli che hanno utilizzato legacy font Khmer (non Unicode) per la conversione verso Unicode (che ha molti benefici), e consentirà i font khmer legacy da importare in Unicode per essere utilizzati rapidamente con un correttore ortografico (piuttosto che passare manualmente e suddividere le parole che, con un documento di grandi dimensioni, può impiegare molto tempo).

Non ho bisogno di precisione al 100%, ma la velocità è importante (soprattutto perché la riga che deve essere divisa in parole Khmer può essere piuttosto lunga). Sono aperto a suggerimenti, ma attualmente ho un grande corpus di parole khmer che sono correttamente suddivise (con uno spazio non interrotto), e ho creato un file di dizionario di probabilità parola (frequency.csv) da usare come dizionario per la parola splitter.

Ho trovato questo codice python here che utilizza il Viterbi algorithm e che presumibilmente funziona veloce.

import re 
from itertools import groupby 

def viterbi_segment(text): 
    probs, lasts = [1.0], [0] 
    for i in range(1, len(text) + 1): 
     prob_k, k = max((probs[j] * word_prob(text[j:i]), j) 
         for j in range(max(0, i - max_word_length), i)) 
     probs.append(prob_k) 
     lasts.append(k) 
    words = [] 
    i = len(text) 
    while 0 < i: 
     words.append(text[lasts[i]:i]) 
     i = lasts[i] 
    words.reverse() 
    return words, probs[-1] 

def word_prob(word): return dictionary.get(word, 0)/total 
def words(text): return re.findall('[a-z]+', text.lower()) 
dictionary = dict((w, len(list(ws))) 
        for w, ws in groupby(sorted(words(open('big.txt').read())))) 
max_word_length = max(map(len, dictionary)) 
total = float(sum(dictionary.values())) 

Ho anche provato ad utilizzare il codice sorgente Java da parte dell'autore di questa pagina: Text segmentation: dictionary-based word splitting ma corse troppo lento per essere di qualche utilità (perché il mio dizionario probabilità parola ha più di 100k termini ...).

E qui è un'altra opzione in python da Detect most likely words from text without spaces/combined words:

WORD_FREQUENCIES = { 
    'file': 0.00123, 
    'files': 0.00124, 
    'save': 0.002, 
    'ave': 0.00001, 
    'as': 0.00555 
} 

def split_text(text, word_frequencies, cache): 
    if text in cache: 
     return cache[text] 
    if not text: 
     return 1, [] 
    best_freq, best_split = 0, [] 
    for i in xrange(1, len(text) + 1): 
     word, remainder = text[:i], text[i:] 
     freq = word_frequencies.get(word, None) 
     if freq: 
      remainder_freq, remainder = split_text(
        remainder, word_frequencies, cache) 
      freq *= remainder_freq 
      if freq > best_freq: 
       best_freq = freq 
       best_split = [word] + remainder 
    cache[text] = (best_freq, best_split) 
    return cache[text] 

print split_text('filesaveas', WORD_FREQUENCIES, {}) 

--> (1.3653e-08, ['file', 'save', 'as']) 

Io sono un newbee quando si tratta di pitone e sono davvero nuovo a tutto reale di programmazione (al di fuori di siti web), quindi per favore abbiate pazienza con me . Qualcuno ha qualche opzione che ritengono funzionerebbe bene?

Answer 1

La libreria ICU (che ha Python e binding Java) ha una classe DictionaryBasedBreakIterator che può essere utilizzata per questo.

Answer 2

Il pitone con l'esempio filesaveas sembra ricorrere all'intera stringa di input (for i in xrange(1, len(text) + 1)), inserendo i risultati migliori nello cache lungo il percorso; ad ogni parola potenziale, è poi la parola successiva (che a sua volta guarderà la parola dopo, e così via), e se questa seconda parola non sembra molto buona, non lo farà salva quel particolare. Si si sente come il runtime O (N!), Dove N è la lunghezza della stringa di input.

Super intelligente, ma probabilmente orribile per tutto tranne compiti semplici. Qual è la parola khmer più lunga che hai? Spero che < 20 caratteri.

Forse se si alimenta l'input in quell'esempio di 20 caratteri alla volta è possibile mantenere il runtime su un valore ragionevole.Inserisci i primi 20 caratteri, succhia la prima parola e poi inserisci l'input rimanente. Se riutilizzi la cache potrebbe fare qualcosa di sciocco come memorizzare parole parziali lungo la strada.

Su una virata completamente diversa, quante parole khmer si formano concatenando due o più parole khmer legali? (simile a "temperino" o "pallacanestro") Se non troppi, potrebbe essere sensato creare una serie di dizionari, separati per lunghezza di parole, mappatura da parola a probabilità di utilizzo.

Dire, la parola khmer più lunga è lunga 14 caratteri; inserire 14 caratteri di input nel dizionario len14, memorizzare la probabilità. Inserire 13 caratteri in len13, memorizzare la probabilità. Feed in 12 caratteri ... fino a 1 in len1. Quindi scegli l'interpretazione con la più alta probabilità, salva la parola, elimina molti caratteri e riprova.

Quindi non fallirà male per ingressi come "I" vs "Immagine", forse gli input più lunghi dovrebbero avere probabilità gonfiate automaticamente?

Grazie per la divertente domanda;) Non sapevo di lingue come questa, piuttosto interessante.

Answer 3

Penso che questa sia una buona idea, così com'è.

Ti suggerisco, quando hai qualche esperienza con esso, di aggiungere alcune regole, che possono essere molto specifiche, ad esempio, a seconda della parola prima, a seconda della parola dopo, a seconda delle parole circostanti, a seconda di una sequenza di parole prima della parola corrente, solo per elencare le parole più frequenti. È possibile trovare un insieme di regole nel progetto gposttl.sf.net, che è un progetto di tagging pos, nel file data/contextualrulefile.

Le regole devono essere utilizzate DOPO che la valutazione statistica è terminata, effettuano alcune regolazioni fini e possono migliorare notevolmente la precisione.