Split a sentence into separate words

Question

I need to split a Chinese sentence into separate words. The problem with Chinese is that there are no spaces. For example, the sentence may look like: 主楼怎么走 (with spaces it would be: 主楼 怎么 走).

At the moment I can think of one solution. I have a dictionary with Chinese words (in a database). The script will:

1. try to find the first two characters of the sentence in the database (主楼),

2. if 主楼 is actually a word and it's in the database the script will try to find first three characters (主楼怎). 主楼怎 is not a word, so it's not in the database => my application now knows that 主楼 is a separate word.

3. try to do it with the rest of the characters.

I don't really like this approach, because to analyze even a small text it would query the database too many times.

Are there any other solutions to this?

Answer 1

Thanks to everyone for you help!

After a little research I've found some working tools (having in mind all your suggestions), that's why I'm answering my own question.

1. A PHP class (http://www.phpclasses.org/browse/package/2431.html)

2. A Drupal module, basically another PHP solution with 4 different segmentation algorithms (pretty easy to understand how it works) (http://drupal.org/project/csplitter)

3. A PHP extension for Chinese word segmentation (http://code.google.com/p/phpcws/)

4. There are some other solutions availabe if you try searching baidu.com for "中文分词"

Sincerely,

Equ

Answer 2

You might want to consider using a trie data structure. You first construct the trie from the dictionary then searching for valid words will be much faster. The advantage is determining if you are at the end of a word or need to continue looking for longer words is very fast.