Mecab algorithm (Mecabアルゴリズム) about mecab

[polm]

The algorithm is described in this paper, "Applying Conditional Random Fields to Japanese Morphological Analysis", though you'll probably have to look at the code with details.

The basic idea is it builds a lattice and then uses the Viterbi algorithm to find the cheapest path through the lattice. The tricky part is handling unknown words, which have dictionary entries (and costs) generated on the fly based on number and type of characters.