3 ms·

I'm interested in this kind of algorithm on principle, and analysis of successfully hurdled engineering problems are probably of interest to most readers of hac

by z0r 15y ago

I'm interested in this kind of algorithm on principle, and analysis of successfully hurdled engineering problems are probably of interest to most readers of hacker news. Please elaborate!

chime 15y ago
I think I posted a few of these ( http://ktype.net/wiki/ http://ktype.net/wiki/ ) on HN as I wrote them but barely got any votes so I wasn't sure if HN was the best avenue for it. When I get some time, I will do a write up on how I built the suggestion engine. Here's the gist: * Built a list of 1m words and phrases (1-4 ngrams) and gave each a weight based on how many different people mentioned it and how often: http://ktype.net/wiki/research:articles:progress_20110209 http://ktype.net/wiki/research:articles:progress_20110209 * Sort this list in the following order: first-letter ASC, word length DESC, weight DESC. About 12MB in size. * For each word/phrase in the sorted list, compute a 4-byte (32 bits) value as follows: First 26 bits = 0s and 1s to indicate which letter is present in the word/phrase. So CAT = 101...1000000 (A = 1, C = 1, T = 1, everything else = 0). Then normalize the weight and store it in the last 6 bits. So that's 1m x 32bits = 4MB of precomputed data. * Build an index containing start-end position of all words of same length that begin with the same letter. Words starting with 'A' of length 20: position 1-200. Words starting with 'A' of length 19: position 201:543. And so on. About 32KB in size. * Upon app init, load the 12MB word list, 4MB precomputed data, and 32KB of index. Takes 10s on iPad1, 5s on iPad2. * When user types 'CAR' (3 characters), find the range of all words of length 3-9 that begin with C. Start position P1 = Start position of 'C' of length 9. End position P2 = End position of 'C' of length 3. Everything in between P1 and P2 is fair game for suggestion. Sometimes this can be as small as 100 words (e.g. user typed XP) or as many as 150000 (user typed ENT). * Now, create a 26bit value from what the user typed, like we did with all the words in our 1m long list. So CAR = 101......100000000. Here's the fun part: For each precomputed 26bit value, AND it with the CAR-bits and count the number of 1s in the result. This tells us how many letters that the user typed, are present in each of the 3-9 length word/phrases that begins with a C. Since this is integer math, even looping through all 1m entries is near instant on the iPad. If least 2 out of 3 characters that the user typed are present in a word/phrase, go to next step. * So user typed 'CAR' and we now have a list of words like 'CATARACTS', 'CRIMSON', 'CARBON, 'CRAYON', 'CHARM', 'CARE', 'CAR', 'CRY' etc. How do we know which one the user is trying to type? Well, depends on which word fits best and how high the weight is. By 'fit', I mean 'CAR' => 'CAMERA' is a better fit than 'CAR' => 'CRAYON' because the letters 'CAR' are in the correct order in the word 'CAMERA' but 'A' and 'R' are flipped in 'CRAYON'. * If we do a distance calculation between the words at this point, it will just match the shortest words that have similar letters. So CAR will match CAR, CRY, CARE and not match CATARACT at all. We want it to match longer words also because those are much harder to spell out. E.g. PMGN should match POMEGRANATE and PYGMALION better than PONG or PIGEON. Spell-checks work by measuring distance between words - http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html but we're not making spell-check. We're making a word-predictor. So we need to find what words fit CAR and PMGN and how well. * Turns out it's easy. To find out the fit, simply remove all letters in the word/phrase that the user did not type. So CAMERA => 'CARA'. 'CRAYON' => 'CRA'. If user typed PMGN, then POMEGRANATE will become PMGN, PIGEON will become PGN. Now take the http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance of what the user typed e.g. 'CAR' and each resulting phrase: CARA, CRA, CAAR, CR, CA etc. Do some funky math with the resulting distance x word length x word weight x exact-match-ness and give it a score. If score > min-fuzzy-value, return it. Else word does not match. The min-fuzzy-value is calculated based on how many words begin with the letter, have the same length etc. If user typed 'ENT', we want min-fuzzy-value to be quite high, if they typed 'QLX', then we want a really low min-fuzzy-value or else there won't be any positive matches. * Once you have at most 100 (or 1000 depending on processor speed) matches that have a high enough score, sort descending by score and return top 3-7 as configured by user. This is just the algo for single word match. The multi-word match is similar but has a lot more conditions to speed things up. But it works significantly better than single word match because it really narrows down the potential matches. Typing 'T' can mean any of the 20,000 words of 2-5 in length. But typing 'T' after 'EIFFEL' really narrows it down. While my approach to word suggestion may seem pretty obvious, what I didn't mention were the 50+ approaches that did not work because of performance, quality, or stability issues. I'd love to hear any questions about it and I can provide my ObjC code (after I clean it up) if someone wants to build on it. Please note I wrote all of the above off the top of my head and not as a detailed research paper. I left out lots of minor optimizations and kludges. Also I'm pretty sure I can describe the indexing and bit-counting better given some free time.
- JoshTriplett 15y ago
  Sounds like you have some interesting algorithms there, but I think you might want to spend some more time looking at well-known algorithms that might make improve both efficiency and accuracy. For efficiency, you might consider one of the various tree-like structures that would allow you to not bother searching every single word. That would become significantly more important with a larger database, or a less powerful device. For accuracy, consider arithmetic coding, and take a look at some of the work and writings from the Dasher project (http://www.inference.phy.cam.ac.uk/dasher/ http://www.inference.phy.cam.ac.uk/dasher/). In addition to their impressive input system, they've done a ton of work on accessibility. Also, depending on your input system, you should consider the possibility of common typos or equivalent; for instance, on a keyboard you'd consider adjacent characters as likely typos.
  - chime 15y ago
    > I think you might want to spend some more time looking at well-known algorithms that might make improve both efficiency and accuracy. I went through hundeds of research papers on the topic and found nothing that could help me. Tries and BSTs are awesome for a lot of things but not what I was trying to do. If you read above, I don't search through each of the 1m words - I narrow down to the letter based on word-length and then find all possible words that match at least 66% of the letters that the user typed. This allows for typos and relaxes the filters. Going from 1m to 1000 words takes under 0.01s on iPad1 because of the bit-counting algo. The hard part is picking the best 5 out of the 1000 that match and is what takes some time. If user types 'CTA', how would pick the best match from hundreds of words like CATARACT, CITADEL, CANTINA, CRUSTACEAN etc.? > For accuracy, consider arithmetic coding, and take a look at some of the work and writings from the Dasher project (http://www.inference.phy.cam.ac.uk/dasher/ http://www.inference.phy.cam.ac.uk/dasher/). In addition to their impressive input system, they've done a ton of work on accessibility. Dasher was one of the inspirations for KType actually. When I came across it years ago, I tried to make it work for my cousin but it requires a lot of dexterity and timing, even when configured properly. And when I looked at it last, it did not support a high-level of word-completion / finishing sentences. On KType, if the user wants to type 'GIVE ME SOME FOOD', they type 'GV', select 'GIVE' on screen, then 'ME' on screen, then type 'S' and select 'SOME' and so on. Additionally, KType can take input from external bluetooth devices and I'm working on making it accept input from bluetooth joysticks, so they wouldn't have to touch the screen at all. I also wrote a simple algo to ignore unintentional touches a user might make if they do not have fine motor skills: http://ktype.net/wiki/research:articles:progress_20111105 http://ktype.net/wiki/research:articles:progress_20111105 > Also, depending on your input system, you should consider the possibility of common typos or equivalent; for instance, on a keyboard you'd consider adjacent characters as likely typos. In addition to handling typos, I offer a special keyboard layout to minimize the amount of movement a user would have to make when typing: http://ktype.net/wiki/research:articles:progress_20110228 http://ktype.net/wiki/research:articles:progress_20110228 Last thing I wanted to do was reinvent the wheel for no reason. The problem is that in this field, most all of the technology is proprietary and even though lot of research is done to invent systems that help others, they are purely research and rarely ship. In the long-term, KType is a system to integrate with other hardware for I/O and provide the user with a single, easy-to-use interface.

by z0r 15y ago

I'm interested in this kind of algorithm on principle, and analysis of successfully hurdled engineering problems are probably of interest to most readers of hacker news. Please elaborate!

chime 15y ago

I think I posted a few of these ( http://ktype.net/wiki/ http://ktype.net/wiki/ ) on HN as I wrote them but barely got any votes so I wasn't sure if HN was the best avenue for it. When I get some time, I will do a write up on how I built the suggestion engine. Here's the gist: * Built a list of 1m words and phrases (1-4 ngrams) and gave each a weight based on how many different people mentioned it and how often: http://ktype.net/wiki/research:articles:progress_20110209 http://ktype.net/wiki/research:articles:progress_20110209 * Sort this list in the following order: first-letter ASC, word length DESC, weight DESC. About 12MB in size. * For each word/phrase in the sorted list, compute a 4-byte (32 bits) value as follows: First 26 bits = 0s and 1s to indicate which letter is present in the word/phrase. So CAT = 101...1000000 (A = 1, C = 1, T = 1, everything else = 0). Then normalize the weight and store it in the last 6 bits. So that's 1m x 32bits = 4MB of precomputed data. * Build an index containing start-end position of all words of same length that begin with the same letter. Words starting with 'A' of length 20: position 1-200. Words starting with 'A' of length 19: position 201:543. And so on. About 32KB in size. * Upon app init, load the 12MB word list, 4MB precomputed data, and 32KB of index. Takes 10s on iPad1, 5s on iPad2. * When user types 'CAR' (3 characters), find the range of all words of length 3-9 that begin with C. Start position P1 = Start position of 'C' of length 9. End position P2 = End position of 'C' of length 3. Everything in between P1 and P2 is fair game for suggestion. Sometimes this can be as small as 100 words (e.g. user typed XP) or as many as 150000 (user typed ENT). * Now, create a 26bit value from what the user typed, like we did with all the words in our 1m long list. So CAR = 101......100000000. Here's the fun part: For each precomputed 26bit value, AND it with the CAR-bits and count the number of 1s in the result. This tells us how many letters that the user typed, are present in each of the 3-9 length word/phrases that begins with a C. Since this is integer math, even looping through all 1m entries is near instant on the iPad. If least 2 out of 3 characters that the user typed are present in a word/phrase, go to next step. * So user typed 'CAR' and we now have a list of words like 'CATARACTS', 'CRIMSON', 'CARBON, 'CRAYON', 'CHARM', 'CARE', 'CAR', 'CRY' etc. How do we know which one the user is trying to type? Well, depends on which word fits best and how high the weight is. By 'fit', I mean 'CAR' => 'CAMERA' is a better fit than 'CAR' => 'CRAYON' because the letters 'CAR' are in the correct order in the word 'CAMERA' but 'A' and 'R' are flipped in 'CRAYON'. * If we do a distance calculation between the words at this point, it will just match the shortest words that have similar letters. So CAR will match CAR, CRY, CARE and not match CATARACT at all. We want it to match longer words also because those are much harder to spell out. E.g. PMGN should match POMEGRANATE and PYGMALION better than PONG or PIGEON. Spell-checks work by measuring distance between words - http://norvig.com/spell-correct.html http://norvig.com/spell-correct.html but we're not making spell-check. We're making a word-predictor. So we need to find what words fit CAR and PMGN and how well. * Turns out it's easy. To find out the fit, simply remove all letters in the word/phrase that the user did not type. So CAMERA => 'CARA'. 'CRAYON' => 'CRA'. If user typed PMGN, then POMEGRANATE will become PMGN, PIGEON will become PGN. Now take the http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance of what the user typed e.g. 'CAR' and each resulting phrase: CARA, CRA, CAAR, CR, CA etc. Do some funky math with the resulting distance x word length x word weight x exact-match-ness and give it a score. If score > min-fuzzy-value, return it. Else word does not match. The min-fuzzy-value is calculated based on how many words begin with the letter, have the same length etc. If user typed 'ENT', we want min-fuzzy-value to be quite high, if they typed 'QLX', then we want a really low min-fuzzy-value or else there won't be any positive matches. * Once you have at most 100 (or 1000 depending on processor speed) matches that have a high enough score, sort descending by score and return top 3-7 as configured by user. This is just the algo for single word match. The multi-word match is similar but has a lot more conditions to speed things up. But it works significantly better than single word match because it really narrows down the potential matches. Typing 'T' can mean any of the 20,000 words of 2-5 in length. But typing 'T' after 'EIFFEL' really narrows it down. While my approach to word suggestion may seem pretty obvious, what I didn't mention were the 50+ approaches that did not work because of performance, quality, or stability issues. I'd love to hear any questions about it and I can provide my ObjC code (after I clean it up) if someone wants to build on it. Please note I wrote all of the above off the top of my head and not as a detailed research paper. I left out lots of minor optimizations and kludges. Also I'm pretty sure I can describe the indexing and bit-counting better given some free time.

JoshTriplett 15y ago
Sounds like you have some interesting algorithms there, but I think you might want to spend some more time looking at well-known algorithms that might make improve both efficiency and accuracy. For efficiency, you might consider one of the various tree-like structures that would allow you to not bother searching every single word. That would become significantly more important with a larger database, or a less powerful device. For accuracy, consider arithmetic coding, and take a look at some of the work and writings from the Dasher project (http://www.inference.phy.cam.ac.uk/dasher/ http://www.inference.phy.cam.ac.uk/dasher/). In addition to their impressive input system, they've done a ton of work on accessibility. Also, depending on your input system, you should consider the possibility of common typos or equivalent; for instance, on a keyboard you'd consider adjacent characters as likely typos.
- chime 15y ago
  > I think you might want to spend some more time looking at well-known algorithms that might make improve both efficiency and accuracy. I went through hundeds of research papers on the topic and found nothing that could help me. Tries and BSTs are awesome for a lot of things but not what I was trying to do. If you read above, I don't search through each of the 1m words - I narrow down to the letter based on word-length and then find all possible words that match at least 66% of the letters that the user typed. This allows for typos and relaxes the filters. Going from 1m to 1000 words takes under 0.01s on iPad1 because of the bit-counting algo. The hard part is picking the best 5 out of the 1000 that match and is what takes some time. If user types 'CTA', how would pick the best match from hundreds of words like CATARACT, CITADEL, CANTINA, CRUSTACEAN etc.? > For accuracy, consider arithmetic coding, and take a look at some of the work and writings from the Dasher project (http://www.inference.phy.cam.ac.uk/dasher/ http://www.inference.phy.cam.ac.uk/dasher/). In addition to their impressive input system, they've done a ton of work on accessibility. Dasher was one of the inspirations for KType actually. When I came across it years ago, I tried to make it work for my cousin but it requires a lot of dexterity and timing, even when configured properly. And when I looked at it last, it did not support a high-level of word-completion / finishing sentences. On KType, if the user wants to type 'GIVE ME SOME FOOD', they type 'GV', select 'GIVE' on screen, then 'ME' on screen, then type 'S' and select 'SOME' and so on. Additionally, KType can take input from external bluetooth devices and I'm working on making it accept input from bluetooth joysticks, so they wouldn't have to touch the screen at all. I also wrote a simple algo to ignore unintentional touches a user might make if they do not have fine motor skills: http://ktype.net/wiki/research:articles:progress_20111105 http://ktype.net/wiki/research:articles:progress_20111105 > Also, depending on your input system, you should consider the possibility of common typos or equivalent; for instance, on a keyboard you'd consider adjacent characters as likely typos. In addition to handling typos, I offer a special keyboard layout to minimize the amount of movement a user would have to make when typing: http://ktype.net/wiki/research:articles:progress_20110228 http://ktype.net/wiki/research:articles:progress_20110228 Last thing I wanted to do was reinvent the wheel for no reason. The problem is that in this field, most all of the technology is proprietary and even though lot of research is done to invent systems that help others, they are purely research and rarely ship. In the long-term, KType is a system to integrate with other hardware for I/O and provide the user with a single, easy-to-use interface.