title: Text segmentation: dictionary-based word splitting
body: <h2>Background</h2>
  
  <p>Split database column names into equivalent English text to seed a data dictionary. The English dictionary is created from a corpus of corporate documents, wikis, and email. The dictionary (<code>lexicon.csv</code>) is a CSV file with words and probabilities. Thus, the more often someone writes the word "therapist" (in email or on a wiki page) the higher the chance of "therapistname" splits to "therapist name" as opposed to something else. (The lexicon probably won't even include the word rapist.)</p>
  
  <h2>Source Code</h2>
  
  <ul>
  <li>TextSegmenter.java @ <a href="http://pastebin.com/taXyE03L" rel="nofollow noreferrer">http://pastebin.com/taXyE03L</a></li>
  <li>SortableValueMap.java @ <a href="http://pastebin.com/v3hRXYan" rel="nofollow noreferrer">http://pastebin.com/v3hRXYan</a></li>
  </ul>
  
  <h2>Data Files</h2>
  
  <ul>
  <li>lexicon.csv - <a href="http://pastebin.com/0crECtXY" rel="nofollow noreferrer">http://pastebin.com/0crECtXY</a></li>
  <li>columns.txt - <a href="http://pastebin.com/EtN9Qesr" rel="nofollow noreferrer">http://pastebin.com/EtN9Qesr</a></li>
  </ul>
  
  <h2>Problem (updated 2011-01-03)</h2>
  
  <p>When the following problem is encountered:</p>
  
  <pre><code>dependentrelationship::end depend ent dependent relationship
  end=0.86
  ent=0.001
  dependent=0.8
  relationship=0.9
  </code></pre>
  
  <p>These possible solutions exist:</p>
  
  <pre><code>dependentrelationship::dependent relationship
  dependentrelationship::dep end ent relationship
  dependentrelationship::depend ent relationship
  </code></pre>
  
  <p>The lexicon contains words with their relative probabilities (based on word frequency): <code>dependent 0.8</code>, <code>end 0.86</code>, <code>relationship 0.9</code>, <code>depend 0.3</code>, and <code>ent 0.001</code>.</p>
  
  <p>Eliminate the solution of <code>dep end ent relationship</code> because <code>dep</code> is not in the lexicon (i.e., 75% word usage), whereas the other two solutions cover 100% of words in the lexicon. Of the remaining solutions, the probability of <code>dependent relationship</code> is <em>0.72</em> whereas <code>depend ent relationship</code> is <em>0.00027</em>. We can therefore select <code>dependent relationship</code> as the correct solution.</p>
  
  <h2>Related</h2>
  
  <ul>
  <li><a href="https://stackoverflow.com/questions/3856630/how-to-separate-words-in-a-sentence-with-spaces">How to separate words in a &quot;sentence&quot; with spaces?</a></li>
  <li><a href="https://docs.google.com/viewer?a=v&amp;pid=sites&amp;srcid=ZGVmYXVsdGRvbWFpbnxkanBkZnN0b3JlfGd4OjMzMTEzYTA5NTk3NjFjOTc" rel="nofollow noreferrer">Top Coder - Text Segmentation Presentation 1/2</a></li>
  <li><a href="https://docs.google.com/viewer?a=v&amp;pid=sites&amp;srcid=ZGVmYXVsdGRvbWFpbnxkanBkZnN0b3JlfGd4OjQ1YmFiZTNhODVjMzY2MmY" rel="nofollow noreferrer">Top Coder - Text Segmentation Presentation 2/2</a></li>
  <li><a href="https://docs.google.com/viewer?a=v&amp;pid=sites&amp;srcid=ZGVmYXVsdGRvbWFpbnxkanBkZnN0b3JlfGd4OjYyN2I4NTA0OTIxZDNlMGE" rel="nofollow noreferrer">Linear Text Segmentation using Dynamic Programming Algorithm</a></li>
  <li><a href="https://docs.google.com/viewer?a=v&amp;pid=sites&amp;srcid=ZGVmYXVsdGRvbWFpbnxkanBkZnN0b3JlfGd4OjUxZmFkNzc0MmMzOTc5ZmI" rel="nofollow noreferrer">Dynamic Programming: Segmentation</a></li>
  <li><a href="https://sites.google.com/site/djpdfstore/text-segmentation-02.pdf?attredirects=0&amp;d=1" rel="nofollow noreferrer">Dynamic Programming: A Computational Tool</a></li>
  </ul>
  
  <h2>Question</h2>
  
  <p>Given:</p>
  
  <pre><code>// The concatenated phrase or database column (e.g., dependentrelationship).
  String concat;
  
  // All words (String) in the lexicon within concat, in left-to-right order; and
  // the ranked probability of those words (Double). (E.g., {end, 0.97}
  // {dependent, 0.86}, {relationship, 0.95}.)
  Map.Entry&lt;String, Double&gt; word;
  </code></pre>
  
  <p>How would you implement a routine that generates the most likely solution based on lexicon coverage and probabilities? For example:</p>
  
  <pre><code>for( Map.Entry&lt;String, Double&gt; word : words ) {
    result.append( word.getKey() ).append( ' ' );
  
    // What goes here?
  
    System.out.printf( "%s=%f\n", word.getKey(), word.getValue() );
  }
  </code></pre>
  
  <p>Thank you!</p>