AJAX autocomplete is fairly simple to implement. However, I wonder how to handle smart tag suggestion like this on SO.

To clarify the difference between autocomplete and suggestion:

• autocomplete: foo [foobar, foobaz]
• suggestion: foo [barfoo, foobar, foobaz], or even better, with 'did you mean' feature: [barfoo, foobar, foobaz, fobar, fobaz]

I suppose I need some full text search in tags (all letters indexed, not just words). There would be no problem to do it witch regex or other patterns for limited number of tags (even client side).

But how to implement this feature for big number of tags?
Is there any particular reason (besides URL) the tags on SO are dash separated? What about Unicode characters in tags?

I store the tags in the table with the following columns: id, tagname. My SQL query returns objects with following fields: id, tagname, count