Updated 2014-06-29 18:12:20 by SEH

if 0 {Richard Suchenwirth 2005-09-02 - SHARK is for Shorthand Aided Rapid Keyboarding, also known as Shapewriter, a research project by IBM Almaden Laboratory [1] . Here's an experiment to play with this concept in Tcl. Check the IBM site whether this concept is patented (it probably is), so best use this only as an illustrative toy.

The idea is that you do a pen (or mouse, with button 1 down) movement on the virtual keyboard, from the first to the last letter. The sequence of "visited" keys is matched against a dictionary according to the rule: if the first and the last letter match, and each character of a word is contained in the sequence, then that word is considered a candidate. Words not in the dictionary can be typed letter by letter (though you get blanks between them).

"Sharked" words are inserted into the text widget on top (alternatives separated by slashes - I was too lazy to add popup menu selection. For the last word, you also see the input string and the result in the window's title bar.

AK Regarding popup-menus, they are not really required. We have a Tk text widget. We can 'tag' the alternatives and arrange for a click on an alternative to select it as the text, it would also removes the other alternatives in its group from the display.
}
package require Tk
set keys {
    b d k g / c a n i m q / f l e s y x / j h t o p v / . . r u w z
}
#-- frequent English words, borrowed from somewhere in the Web
set words {
    about after all am an and are as at
    back bad be because been before being between big but by
    came can come could country
    day days debts did different do dollars down
    even every  first for found from
    general get go going good got great
    had has have he hello her here him his
    if in input interest into is it its  just  kick kind
    large last like little look
    made make man many may me more most must my
    new no not now  of off old on one only or other our out over
    people please power public
    said saw see shark she since so some still such system
    take test than that the their them then there these they this through
    time to today two  under up upon  very
    war was we well went were what when where which while who will
    with world would writing years you your
}
foreach word $words {set dic($word) ""}

#------------------ Callback for bindings
set buffer ""
set last ""
proc down {w key} {
    $w itemconfig key    -fill white
    $w itemconfig k-$key -fill yellow
    set ::buffer $key
    set ::last   $key
}
proc pass {w x y} {
    set id  [$w find closest $x $y]
    set key [string index [lindex [$w gettags $id] 0] end]
    if {$::last ne "" && $key ne $::last} {
        $w itemconfig k-$key -fill orange
        append ::buffer $key
        set    ::last   $key
    }
}
proc up {w x y t} {
    set id    [$w find closest $x $y]
    set ::last ""
    $t insert insert "[join [lookup $::buffer] /] "
}
#----------------------- dictionary "logic" 
proc lookup string {
    switch [string length $string] {
        1       {set candidates $string}
        2       {set candidates [array names ::dic $string]}
        default {
            set first [string index $string 0]
            set last  [string index $string end]
            set candidates {}
            foreach word [array names ::dic $first*$last] {
                if [contained [dedup $word] $string] {
                    lappend candidates $word
                }
            }
        }
    }
    wm title . $::buffer/$candidates
    set candidates
}
proc contained {word string} {
    string match [join [split $word ""] *] $string
}
if 0 {

In testing, I found that duplicated letters (as n,s,e in Tennessee) are a bit difficult to write, so I added this de-duplicator that reduces duplicate letters to a single one, e.g. dedup Tennessee -> Tenese :
}
proc dedup string {
    set res  ""
    set last ""
    foreach char [split $string ""] {
        if {$char ne $last} {append res $char}
        set last $char
    }
    set res
}

foreach op {+ - * /} {proc $op {a b} "expr {\$a$op\$b}"}
#------------------------ Demo UI
set   w [canvas .c]
pack $w -fill both -expand 1
set t [text $w.t -width 40 -height 5 -wrap word]
$w create window 0 0 -window $t -anchor nw
set x 30
set y 138
 
foreach key $keys {
    switch -- $key {
        / {set x 30; incr y 28}
        . {incr x 28}
        default {
            set id [$w create rect $x $y [+ $x 26] [+ $y 26] -fill white]
            $w itemconfigure $id -tag [list t-$key k-$key key]
            $w create text [+ $x 13] [+ $y 13] -text $key -tag t-$key
            $w bind t-$key <1>               [list down $w $key]
            $w bind t-$key <B1-Motion>       [list pass $w %x %y]
            $w bind t-$key <ButtonRelease-1> [list up   $w %x %y $t]
            incr x 28
        }
    }
}
 
wm geometry . 240x280+0+0
bind . <Up> {exec wish $argv0 &; exit}
bind . <F1> {console show}

if 0 {

After downloading this page via GPRS, the Shark runs pretty nicely on my HTC Magician too. Pascal reported that on another Windows/CE device, the recognition stopped after a few letters. - 2005-09-03 Added the dedup function, as well as "hello" and "world" to the dictionary :^)

LES "Illustrative toy" indeed. Too small a dictionary will fail to recognize many useful words. Too long a dictionary will plague you with false positives. Here is a sample of my attempts with a 47,000-entry dictionary (less than 10% of the entire English language), to save some bypassers' time:
 ATTEMPT        RESULT
 this:          this/toss
 is:            is
 interesting:   interesting/insetting/inning
 power:         poor/pour/purr
 power:         putter/power/peer/poor/pour/per/purr/potter/pouter
 advertising:   allotting/adversing/averting/advertising/along/atoning/aping/adopting/altering/adding/alerting/adhering/advising/apprising/adoring/arising/averring/adorning/adapting/addressing
 introspection: in/icon/iron/inspection/inion/inn/ion/intonation/intention/introspection
 programming:   panning/potting/pining/priming/porting/pang/prong/ping/pig/poring/posing/pinning/prosing
 frustration:   fain/fern/fusion/fatten/flatten/fan/fen/fin/fun
 prototype:     pope/pore
 theory:        toy/try/tty
 never:         never/nor/noter
 forever:       four/fleer/floor/flour/forever/flutter/freer/for/fur/footer/fluter/floorer/fetter/fever

Enjoy your patent, whoever you patent holder are. :-)

RS Thanks for stress-testing :) Your examples show that the word matching obviously can do with some refinements... Also, I've started to play with designing the key layout differently from IBM's model, but no results yet.

escargo This may be one of those cases where either a known word-frequency distribution would be helpful, or a heuristic of moving the chosen word to (or toward) the front of the list would allow a self-organizing list to make support more likely choices.

Zarutian Would it be possible to use a mouse gestureing method instead of lexicon?

What I would have said is: would it be possible to use the endpoint coordinates from mouse gesture instead of relying on lexicon? RS: As the target is to write words, you'd have to spell them letter by letter, as e.g. demonstrated in ReadME - a simple online character recognizer. But the SHARK project claims that one (maybe complex) gesture should be enough to write one word, and then of course you need a lexicon.

Zarutian I think you misunderstood me.

I am not proposing an OCR system like ReadME - a simple online character recognizer.

But a system which uses endpoints(vertices?) of the stylus-drawn curve to determine which letter buttons on the virtual keyboard to activate and in which order.

http://zarutian.cjb.net/2005/myndir/atomik-shark-vertexes-example.png <- image missing 1, 2, 3 are the vertexes in that order drawn.

LES on 2005 November 02: This concept [2] seems to work better.

escargo 3 Nov 2005 - The relative resource requirements ought to be markedly different, given the dynamic nature of Dasher.