title: A Viable Solution for Word Splitting Khmer?
body: <p>I am working on a solution to split long lines of Khmer (the Cambodian language) into individual words (in UTF-8).  Khmer does not use spaces between words.  There are a few solutions out there, but they are far from adequate (<a href="http://sourceforge.net/projects/khmer/files/Khmer%20Word%20Breaking/" rel="nofollow noreferrer">here</a> and <a href="http://www.panl10n.net/english/Outputs%20Phase%202/CCs/Cambodia/MoEYS/Software/2008/Windows/KhmerLineBreaking.zip" rel="nofollow noreferrer">here</a>), and those projects have fallen by the wayside.</p>
  
  <p>Here is a sample line of Khmer that needs to be split (they can be longer than this):</p>
  
  <blockquote>
    <p>ចូរសរសើរដល់ទ្រង់ដែលទ្រង់បានប្រទានការទាំងអស់នោះមកដល់រូបអ្នកដោយព្រោះអង្គព្រះយេស៊ូវ ហើយដែលអ្នកមិនអាចរកការទាំងអស់នោះដោយសារការប្រព្រឹត្តរបស់អ្នកឡើយ។</p>
  </blockquote>
  
  <p>The goal of creating a viable solution that splits Khmer words is twofold: it will encourage those who used Khmer legacy (non-Unicode) fonts to convert over to Unicode (which has many benefits), and it will enable legacy Khmer fonts to be imported into Unicode to be used with a spelling checker quickly (rather than manually going through and splitting words which, with a large document, can take a very long time).</p>
  
  <p>I don't need 100% accuracy, but speed is important (especially since the line that needs to be split into Khmer words can be quite long).
  I am open to suggestions, but currently I have a large corpus of Khmer words that are correctly split (with a non-breaking space), and I have created a word probability dictionary file (frequency.csv) to use as a dictionary for the word splitter.</p>
  
  <p>I found this python code <a href="https://stackoverflow.com/questions/195010/how-can-i-split-multiple-joined-words">here</a> that uses the <a href="http://en.wikipedia.org/wiki/Viterbi_algorithm" rel="nofollow noreferrer">Viterbi algorithm</a> and it supposedly runs fast.  </p>
  
  <pre><code>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 &lt; 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()))
  </code></pre>
  
  <p>I also tried using the source java code from the author of this page: <a href="https://stackoverflow.com/questions/4580877/text-segmentation-dictionary-based-word-splitting">Text segmentation: dictionary-based word splitting</a> but it ran too slow to be of any use (because my word probability dictionary has over 100k terms...).</p>
  
  <p>And here is another option in python from <a href="https://stackoverflow.com/questions/2174093/python-word-splitting">Detect most likely words from text without spaces / combined words</a>:</p>
  
  <pre><code>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 &gt; best_freq:
                  best_freq = freq
                  best_split = [word] + remainder
      cache[text] = (best_freq, best_split)
      return cache[text]
  
  print split_text('filesaveas', WORD_FREQUENCIES, {})
  
  --&gt; (1.3653e-08, ['file', 'save', 'as'])
  </code></pre>
  
  <p>I am a newbee when it comes to python and I am really new to all real programming (outside of websites), so please bear with me.  Does anyone have any options that they feel would work well?</p>