Una soluzione praticabile per il khmer che divide le parole?

Question

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

Ecco una linea di campionamento di Khmer che deve essere divisa (possono essere più lunghi di questo):

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

L'obiettivo di creare una soluzione praticabile che divide le parole Khmer è duplice: incoraggerà coloro che hanno usato i caratteri Khmer Legacy (non UNICODE) per convertirsi in Unicode (che ha molti vantaggi) e consentirà di importare i caratteri Khmer legacy in Unicode da usare rapidamente con un controllo ortografico (piuttosto che passare manualmente e dividere le parole che, con un documento di grandi dimensioni, possono richiedere molto tempo).

Non ho bisogno di una precisione del 100%, ma la velocità è importante (soprattutto perché la linea 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 divise (con uno spazio non di rottura) e ho creato un file di dizionario di probabilità di parola (frequenza.csv) da utilizzare come dizionario per il Splitter di parole.

Ho trovato questo codice Python qui che usa il Algoritmo Viterbi E presumibilmente funziona velocemente.

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 a utilizzare il codice Java di origine dall'autore di questa pagina: Segmentazione del testo: divisione di parole basate sul dizionario Ma ha funzionato troppo lentamente per essere di qualsiasi uso (perché il mio dizionario di probabilità della parola ha oltre 100.000 termini ...).

Ed ecco un'altra opzione in Python da Rileva le parole più probabili dal testo senza spazi / parole combinate:

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'])

Sono un Newbee quando si tratta di Python e sono davvero nuovo per tutte le vere programmi (al di fuori dei siti Web), quindi per favore abbi pazienza. Qualcuno ha delle opzioni che ritengono funzionare bene?

Answer 1

La libreria ICU (che ha Pitone e i binding java) ha a Dictionarybased Breakingeterator Classe che può essere utilizzata per questo.

Answer 2

Il Python con esempio filesaveas sembra ricorrere attraverso l'intera stringa di input (for i in xrange(1, len(text) + 1)), riempire i migliori risultati in cache lungo la strada; Ad ogni potenziale parola, esso poi inizia a guardare il prossimo Word (che a sua volta guarderà la parola dopo, e così via), e se quella seconda parola non sembra molto buona, non salverà quella particolare. Esso sente Come O (N!) Runtime, dove n è la lunghezza della stringa di input.

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

Forse se si dà da mangiare all'input in quell'esempio 20 caratteri alla volta puoi mantenere il runtime a qualcosa che si avvicina ragionevole. Nutri nei primi 20 carattere, succhia la prima parola e quindi alimenta l'input rimanente. Se riutilizzi la cache, potrebbe fare qualcosa di sciocco come le parole parziali del negozio lungo la strada.

Su una virata completamente diversa, quante parole Khmer sono formate concatenando due o più parole legali di Khmer? (Simile a "Penknife" o "Basketball") Se non troppi, potrebbe avere senso creare una serie di dizionari, separati per lunghezza della parola, mappando dalla parola alla probabilità di utilizzo.

Di ', la parola Khmer più lunga è lunga 14 carattere; alimentare 14 caratteri di input in len14 Dizionario, conservare la probabilità. Nutrire 13 caratteri in len13, conserva la probabilità. Nutri in 12 caratteri ... fino a 1 in len1. Quindi scegli l'interpretazione con la massima probabilità, salva la parola, spoglia così tanti personaggi e riprova.

Quindi non fallirà gravemente per input come "I" vs "Immagine", forse input più lunghi avrebbero dovuto avere probabilità gonfiate automaticamente?

Grazie per la domanda divertente;) Non conoscevo alcuna lingua come questa, piuttosto bella.

Answer 3

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

Ti suggerisco, quando hai qualche esperienza con esso, aggiungi 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 corrente parola, solo per elencare quelli più frequenti. È possibile trovare una serie di regole nel progetto GPOSTTL.SF.NET, che è un progetto di tagging POS, nei dati del file/contestualRuleFile.

Le regole dovrebbero essere utilizzate dopo che la valutazione delle statistiche è terminata, effettuano una messa a punto e possono migliorare notevolmente la precisione.