Aim

Segment English Sentences without Spaces.

In the Coding book, the space character has no corresponding codon. Therefore, we need to segment English sentences without Spaces. For example, the input sentence is "Iwanttostudybiologyeveryday", the output of the results should be: "i want to study biology everyday". In our program, firstly we implement word graph scanning based on prefix tree structure and construct DAG(Directed Acyclic Graph) to obtain all English word segmentation results, secondly we use IF-IDF(Term Frequency-Inverse Document Frequency) model and maximum sharding method to obtain the optimal word segmentation results.

Programming

1.Preprocessing entered data.
Algorithm: Determine whether there are numbers in the entered data and whether there are empty data.
The English sentences that we entered have no Spaces. And they satisfy the following conditions:
a.The English sentences do not contain any characters except letters, such as numbers, punctuation marks, etc. In the construction of our Coding Book, we establish the correspondence between letters and codons. Therefore, the digital and punctuation information will be lost during the period of decryption. Our software does not support these characters.
b. The length of English sentences is no longer than 50. As the length of English sentences grows longer, other introns appear in the codons, and this information will be cut in the organism. The probability of appearing introns increases with length. Therefore, we limit the length of the sentence to 50 characters.

2.Find all possible word combinations.
Algorithm: Achieve efficient word graph scanning based on a prefix tree structure. Build a DAG(Directed Acyclic Graph) to obtain all English word segmentation results.
In this process, we constructed a prefix tree tree and a directed acyclic graph.
A prefix tree, is a kind of search tree. We use the prefix tree for word frequency statistics. In this prefix tree, the root is associated with the empty string, and all the descendants of a node have a common prefix. In the search, we start from the root node and connect each character passing through the road as the corresponding string of the node. Using the prefix tree structure allows us to improve the speed of query words and the efficiency of search.
The figure is a prefix tree structure of ever, very, every, go and good.

After constructing the prefix tree, we build a directed acyclic graph. In our DAG, each node is a letter, and each letter points to its next letter. If we detect a word, we add a directed edge between the first letter and the last letter of the word. Therefore, we can traverse all the segmentation results according to the DAG we constructed.
For example, if the sentence is "Iwanttostudybiologyeveryday", assumes that the word in the prefix tree as follows:

“and, biology, cat, day, ever, every, everyday, fat, guess, he, I, jeep, kangaroo, learn, mom, noon, opt, peach, quit, rust, study, to, you, very, want, xylan, yellow, zoom”

Then the DAG is as shown in the figure.

3.Find the most probable combination
Algorithm: Use IF-IDF(Term Frequency-Inverse Document Frequency) model and maximum sharding method to obtain the optimal word segmentation results.
TF-IDF is a statistical method that can be used to assess how important a word is to this document. The importance of a word increases proportionately as it appears in a document, but decreases inversely as it appears in the corpus. Its formula is as follows:

We can obtain the possibility of each word segmentation method by calculating TF-IDF, so as to find the most probable combination. In order to improve the efficiency of calculation, we use the idea of dynamic programming to carry out calculation.
For example, for the word “everyday”, we have the possible word combinations: “ever, every, very, day, everyday”.

We need to calculate:

(“xxx” means the TF-IDF value of the word xxx)
route[9]=0; e-v-e-r-y-d-a-y
...
route[6]=max(“day”+route[9], “d”+route[7])=“day”+route[9] e-v-e-r-y-day
...
route[2]=max(“very+route[6], “v”+route[3])=“very+route[6] e-very-day
route[1]=max(“ever”+route[5], “every”+route[6], “everyday”+route[9])
= “everyday”+route[9] everyday
So, the most probable combination is “everyday”.