Move over T9, here comes Swype | Hacker News Reader

Move over T9, here comes Swype

news.cnet.com

40 pointsttol24 comments

The first thing that came to mind when I saw this preso was "What algorithm are they using to find the words?" The problem looks something like: Given a string of characters, find all possible words that start and end like the string of characters and use any number of characters in between.

The best I can come up (after not so much thinking about it) with is using Bloom Filters. Precompute the bit vector for every word in your dictionary, then after they swype, compute a vector for the string of characters and run it up against all the words in your dictionary that start and end with the same letters. Still kind of an expensive linear search, albeit fast (since it's just boolean AND).

You also get a hint from direction changes. As far as I can tell, direction changes almost always indicate that the current letter is in the word, though not every letter gets a direction change.

I would have to go with what Natrius said. It's probably based on the stroke directions. The technology is probably very similar to that used to recognize Chinese writing.

The first thing that came to mind was "Newton," which used stroke-recognition for recognizing letters. I doubt it's actually computing letters on the fly, I go along with your thought that you precompute vectors for each word in the dictionary. My thought is that the vectors are probably very simple. They may start with a specific letter, but after that I'm guessing they are very forgiving of inaccuracies. A rough direction and distance is probably enough to disambiguate words from each other.

I'm guessing it precomputes a tree for the dictionary. With each stroke, it drills down the tree along the most likely path. If it runs out of nodes, it backtracks and tries a more likely path somewhere,possibly using a precomputed list of vectors most likely to be mistaken for each other.

That gives On for the best case.

I doubt they use bloom filters (or any other hash-based algorithm) because hashes by their design are a quick way to reference something well defined. A gesture is anything but and you need something a lot more fuzzy and flexible than hashes.

I'd think that they try to calculate the focus of each direction change and see what letter it landed on, then try a fuzzy match to words that have the smallest hamming distance between their input. After you get a good approximation of all the letters, then you can try hashing techniques.

Also, pivoting on first and last letter of each word isn't fool-proof, as the first and last letters are also not guaranteed to be hit dead-on.

They just need to work on getting consumers educated more than T9 did. It's amazing how many times I have explained and demo'd T9 to people--vast numbers of people just don't get it and use multi-tap instead. After a couple of minutes T9 is way faster, but there is usually no tutorial and people get frustrated when it's not doing what they think it should (multitap).

as a foreigner, I hate T9. The first thing I do when I start using a new phone is to turn it off. It just doesn't work with short names, foreign words (or my name), or common sms slang.

I hope this is better.

Multi-language support is tough, but some implementations are better than others (there are lots of different versions of T9, you're just stuck with whatever your phone has). The latest version of T9 has support for using multiple languages at once, but most phone makers don't advertise what version of T9 they ship.

Actually, I'm a foreigner and I find typing using T9 much faster, especially because there are not as many ambiguous words (when using numeric pad) as in English.

the iphone app "writingPad" uses this input method

qwerty evenly spreads commonly used keys between both sides so that you can type fast with two hands; seems like exactly what you wouldn't want with this tech.

Actually that's not true. Qwerty is a very bad layout for keyboards. The guy who invented it was named Qwerty. It was originally designed for typewriters and to be difficult to use to force the typist to slow down to reduce mistakes. Many alternate layouts have been proposed over the years but Qwerty became the defacto standard because it was so widely used by businesses with typewriters. That's what people learned and we've been stuck with it ever sense.

The fact that you can spell 'typewriter' with only keys from the top row might have something to do with the early popularity of that arrangement...

Of course everyone in the know prefers 'DHIATENSOR'.

Wikipedia partially disagrees: http://en.wikipedia.org/wiki/Qwerty

It slows you down to prevent jams. The guy's name was Sholes.

Actually, it's not supposed to slow you down. It's supposed to make sure you're normally hitting keys that are far apart, which means the hammers won't interfere with each other. QWERTY is a pretty good layout because of it. The next letter you try to type is rarely in the domain of the finger that just pressed down, meaning you can line up a number of keys to be pushed at once.

In the Design of Everyday Things, Donald Norman talks about keyboard design a lot. QWERTY is really good, so switching to layouts that are only slightly better (dvorak) end up not being worth the time and effort.

I saw the demo live and it looked great with a stylus... so-so with touch and worse on a phone. Still has work to do.

Definitely innovative, though I wonder if not lifting fingers from the screen helps all that much.

I watched this live at Techcrunch50 and I had mixed reactions. First, it is a rather technically interesting way to do text input. Watching how the experienced developer was playing with it, I could sense how it could feel like writing cursive English letters as whole words.

For the average user though, I just don't see how it catches on. People are fairly split over whether they prefer phones with traditional button keyboards or if they love the touchscreen interface from the iPhone. I love the iPhone because I hated stencils. I get more screen real estate. Its easier for me to do typing on the iPhone than any other smart phone I ever used.

It honestly looked like the demonstrator was scribbling on the screen. I had to look twice a couple of times to make sure it was a live demo and not fake.

this catches on, i say within 5 yrs this tech is on virtually all touchscreen devices. people adapt. thats just how it goes. before txt mssgs came out , how many ppl typed mssgs on the key pad of a phone?

Not a fan at all. I understand how the creator might have put pressure on himself to develop a new relevant solution, but this is nothing short of counterintuitive. Why would you develop a text input method that forces the user to use one finger?

Because the input device is so small that there is no room to use multiple fingers effectively? Because that is the way people use mobile touch screen devices? (Hold the device with one hand, poke/type with the other)

How many new touchscreen-only devices are coming out with screens so small that this solution is feasible?

A lot since the iPhone shows how well it works.

How many people use more than one finger on the screen and how often?

Yes. And who says this is the last and final version?

Reply on news.ycombinator.com