Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Try a stochastic regular grammar (equivalent to hidden markov models) with the following rules:</p> <pre><code>for every word in a dictionary: stream -&gt; word_i stream with probability p_w word_i -&gt; letter_i1 ...letter_in` with probability q_w (this is the spelling of word_i) stream -&gt; letter stream with prob p (for any letter) stream -&gt; epsilon with prob 1 </code></pre> <p>The probabilities could be derived from a training set, but see the following discussion. The most likely parse is computed using the Viterbi algorithm, which has quadratic time complexity in the number of hidden states, in this case your vocabulary, so you could run into speed issues with large vocabularies. But what if you set all the p_w = 1, q_w = 1 p = .5 Which means, these are probabilities in an artificial language model where all words are equally likely and all non-words are equally unlikely. Of course you could segment better if you didn't use this simplification, but the algorithm complexity goes down by quite a bit. If you look at the recurrence relation in the <a href="http://en.wikipedia.org/wiki/Viterbi_algorithm" rel="nofollow">wikipedia entry</a> you can try and simplify it for this special case. The viterbi parse probability up to position k can be simplified to <code>VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l)</code> You can bound l with the maximim length of a word and find if a l letters form a word with a hash search. The complexity of this is independent of the vocabulary size and is <code>O(&lt;text length&gt; &lt;max l&gt;)</code>. Sorry this is not a proof, just a sketch but should get you going. Another potential optimization, if you create a trie of the dictionary, you can check if a substring is a prefix of any correct word. So when you query text[k-l:k] and get a negative answer, you already know that the same is true for text[k-l:k+d] for any d. To take advantage of this you would have to rearrange the recursion significantly, so I am not sure this can be fully exploited (it can see comment).</p>
    singulars
    1. This table or related slice is empty.
    1. POFind the words in a long stream of characters. Auto-tokenize
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USpiccolbo
    1. USpiccolbo
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COActually, I just convinced myself that you can use the potential optimization I described. Imagine a matrix TxT where T is the length of the text. An entry (i,j) is 0 if text[i,j] is a word, else is 1. Now if you fill this (you need only a diagonal band up to the max word length) with a nested loop for i: for j: then as soon as you realize that text[i:j] is not a prefix of any word, you can fill the rest with 1s. This gives you an advantage if you use a sparse representation, like a defaultdict that defaults to 1, so that you actually need to write only the 0s.
      singulars
      1. PO
      1. USpiccolbo
    2. COThis form of recursion is the first known example of dynamic programming and is found in a paper by Bellman from the 60's (the application is signal processing)
      singulars
      1. PO
      1. USpiccolbo
    3. COTo make it more accurate you could use a text corpus to derive probabilities, see for instance http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html, problem 3 and look even at pair of words or more, introducing rules like stream -> word_i word_j stream. You could also use existing ngram data, like the huge one released by Google (not free and noncommercial use though). But there is a computational cost to pay.
      singulars
      1. PO
      1. USpiccolbo
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload