利用鍵區的多字符鍵輸入字母數字數據的設備和方法

2023-05-31 02:26:11

專利名稱：：利用鍵區的多字符鍵輸入字母數字數據的設備和方法
技術領域：
：本發明涉及數據的鍵區輸入。更具體地，本發明涉及利用給一個鍵分配多於一個字母數字字符的鍵區來輸入字母數字數據。
背景技術：
：歷史上，傳統的"轉盤式"電話包括具有10個手指孔的轉盤，10個手指孔代表數字l-9和0，這使人能夠順序地對要呼叫的所需電話號碼的每個數字位進行撥號。隨著電晶體的時代的到來，具有包括被標記為l-9和0的IO個數字鍵的雙音多頻(DTMF)鍵區的電子電話得到廣泛使用並完全取代了傳統的轉盤式電話。傳統的DTMF鍵區一般包括另外兩個被標記為*和#的非數字鍵。與數字鍵組合，傳統DTMF鍵區的外形因而包括一個3x4的布局，共有12個鍵，其中0鍵位於第4排，在*和#鍵之間。DTMF鍵區的製造者還很有遠見地給數字鍵(除了鍵1)分配並標記了英語字母表的26個字母，以允許DTMF鍵區輸入字母數字數據。通常——如果不是所有都是的話-鍵2被標記以字母A、B和C,鍵3被標記以D、E和F，鍵4被標記以G、H和I，鍵54皮標記以J、K和L，鍵6被標記以M、N和O，鍵7被標記以P、Q、R和S，鍵8被標記以T、U和V,鍵9被標記以W、X、Y和Z。利用適當的解碼電路設計了各種"多次敲擊"技術，以允許通過多次敲擊包含被分配有所期望的字母字符的鍵的鍵，來選擇該字母字符。最流行的多次敲擊技術包括多次按下被標記以所期望的字母字符的鍵，按的次數等於該字母字符在該鍵上的位置，然後等待默認的超時時間或按下不同的鍵。例如，當期望字母B時，按下鍵2兩次，因為字母B位於鍵2上的第二個位置。相應地，當期望字母C時，按4下鍵2三次，因為字母C位於鍵2上的第三個位置。教導多次敲擊技術和適當的解碼電路的代表性早期專利包括US4,307,266、US4,532,378和US4,608,457。字母數字DTMF鍵區的早期實現使聾人可利用傳統電話來交流。在二十世紀八十年代，具有字母數字DTMF鍵區的電話成為需要輸入字母數字數據的交互式語音應答電話系統所必不可少的。在二十世紀九十年代，字母數字DTMF鍵區被廣泛用來為電話短消息服務(SMS)輸入字母數字數據。最近，傳統的字母數字DTMF鍵區和其他把多個字母數字字符分配給一個或多個鍵的簡化鍵字母數字鍵區，已經普遍用在其他應用的主機上以輸入字母數字數據，諸如但不限於個人數字助理和裝置。不幸的是，如上所述，傳統的多次敲擊技術必須多次按一個鍵以"滾，，過與該鍵相關聯的多個字符，從而選擇單個字母數字字符。例如，在上面提到的傳統DTMF鍵區中，必須將相應的鍵2-9按兩次來選擇字母B、E、H、K、N、Q、U和X，按三次來選擇字母C、F、I、L、O、R、V和Y，而必須將相應的按鍵7和9按四次才能選擇字母S和Z。實際上，只要多個字母數字字符被分配給簡化鍵字母數字鍵區上的特定鍵，就需要對相應鍵進行額外按壓以滾過相關聯的字母數字字符。現在有各種技術用於使得滾過並選擇與簡化鍵字母數字鍵區的多字符鍵相關聯的特定字母數字字符所需的對該多字符鍵的按壓次數最小。一種普通的方法是採用字典資料庫，然後根據與字典中最常用的詞相匹配的字母數字字符的輸入，來預測所期望的字母數字字符。伊J:i口，TegicCommunications(hrtp:〃www.t9.com)提供一種用商標"T9"標識的基於字典的軟體應用，其讀取一串擊鍵(keystroke)，然後根據特定於語言(language-specific)的字典，順序地提供對應於與這些鍵相關聯的字母數字字符的最常用的詞。為了說明這一點，英語字典資料庫可包括詞"how"並且將其優先作為與DTMF擊鍵序列4-6-9相關聯的最常用的詞。然後，一旦輸入擊鍵序列4-6-9，詞"how"被顯示並供用戶選擇。如果"how"是所期望的詞，則只需擊鍵三次即可選擇該詞(與上面討論的多次敲擊技術相比，多次敲擊技術需要擊鍵六次)。如果"how"不是所期望的詞，用戶隨後可以再按下表示"下一個，，鍵的鍵，以指示程序顯示下一個最常用的詞。如果反覆按"下一個"鍵也不能顯示所期望的詞，則可以使用多次敲擊的方法來將期望的詞手工輸入到字典中。T9已經獲得了實質性的商業成功，但是需要可觀的存儲器來存儲特定於語言的字典。而且，由於字典是特定於語言的，因此T9特別不適合多語言使用或經常採用首字母縮寫詞、縮略語、科學詞彙等等其他不那麼常見的實現方式。屬於TegicCommuniations，Inc.的關於其T9軟體的代表性專利美國專利標題6,307,549Reducedkeyboarddisambiguatingsystem6,307,548Reduced3keyboairddisambiguatingsystem6,286,064Reducedkeyboardandmethodforsimultaneousambiguousandunambiguoustextinput6,011,554Reducedkeyboarddisambiguatingsystem5,953,541Disambiguatingsystemfordisambiguatingambiguousinputsequencesbydisplayingobjectsassociatedwiththegeneratedinputsequencesintheorderofdecreasingfrequencyof5,945,928Reducedkeyboajcddisambiguating*systemfortheSf818,437Reducedkeyboarddisambiguatingcomputer另一個用來使滾過以選擇與筒化鍵字母數字鍵區的多個鍵相關聯的特定字母數字字符所需的對該多個鍵的按壓次數最小的普遍方法是採用基於語言學的算法，該算法基於預先定義的語言學規則來預測所期望的字母數字字符。例如，EatoniErgonomics,Inc.提供一種以商標"Letterwise"銷售的軟體程序，該程序包括大量的語言學規則，該規則基於先前輸入的其他字符來預測所按下的多字符鍵的期望字母。語言學規則的一個簡單例子是，只要先前輸入的字母是字母"q",則在按下多字符(T，U和V)鍵8之後提供字母"u"，這是因為無論字母"t，，還是"v，，在語言學上都不合適。所採用的語言學理論在Eatoni的專利中#/>開，所述專利包括標題為"Touch-typabledevicesbasedonambiguouscodesandmethodstodesignsuchdevices，，的美國專利US6,885,317和標題為"MethodandApparatusforImprovedMulti-TapTextInput"的美國專利US6，219，731。類似於基於字典的T9，基於語言學的Letterwise是特定於語言的。Letterwise可更適用於採用不太常見的詞的科學應用，這是因為即使科學詞彙通常也是基於語言學的，並且較少的擊鍵也可能是必要的。但是，T9和Letterwise都不能預測不常見的首字母縮寫或縮略語，諸如用於軍事應用中的那些。可以在下列美國專利中找到公開了用於基於先前輸入的字符(或詞)來預測期望字符(或詞)的算法的其他代表性專利美國專利標題5,952,942MethodandDeviceforInputofTextMessagesfrom3Keypaid5,974,121AlphanumericMessageCo卿osingrMethodusingTelephoneKeypad,6^052,443AlphanumericMessageComposingMethodusingTelephoneKeypadApparatusandMethodforInputtingIdeographicCharacters6,137,867AlphanumeiricMessageComposingMethodusingTelephon錢Keypad5,828,991SentQiiceReconstructionusingWordAmbiguityResolution5,960,385sentenceReconstructionusingWordAmbiguityResolution5,031,206MethodandApparatusforIdentifyingWordsEnteredonDTMFPushbuttons5,903,630MethodandApparatusforSpecifyingAlphanumericInformationwithsTeLephoneKeypadS,150,9S2PredictiveDataEntxyMethodforaKeyboard6,346,894鵬thodandSystemforIntelligentTextEntryonaUumei:icKeypad6,643,371MethodandApparatusforAlphanumericDataEntry5,911,485PredictiveDataEntryMethodforaKeypad6,799,303SpeedTypingApparatusand胸thod
發明內容因此，本發明的一個目的是提供可克服前面提到的現有技術方法的不足的改進，並提供對現有技術的進步有顯著貢獻的改進。本發明的另一個目的是提供一種設備和方法，用於利用給每個鍵分配一個或多個字母數字字符的鍵區來輸入字母數字數據，其中定義與所按的鍵相關聯的預測的規則樹是基於先前對字符的選擇而建立的，並基於該規則樹先前正確定義預測的次數而被加權，從而提高預測期望字符的概率，並快速適應具有不同語言風格或詞彙的不同用戶。前述已經概述了本發明的有關目的。這些目的應該被解釋為僅僅說明了本發明更多顯著特點和應用中的一些。可通過將所公開的發明以不同的方式應用，或者在本公開範圍內修改本發明，而得到許多其它有益結果。因此，除了由權利要求限定的發明範圍，還可結合附圖，參考
發明內容和對優選實施例的詳細描述來獲得本發明的其它目的和對本發明更完全的理解。出於概括本發明的目的，本發明包括一種方法和設備，用於預測被按下的簡化鍵鍵區的多字符鍵的所期望的字母數字字符。因而可利用DTMF和具有多字符鍵的其它鍵區來輸入由字符(在下文中是字符l、字符2、字符3等)組成的詞。8更具體地，當特定鍵被按下以選擇字符1時，從存儲器中調用與和該鍵相關聯的字符之一相對應的第一字符規則列表，並顯示該字符。用戶可通過等待一默認時間段或通過選擇一個不同的鍵來選擇該字符，隨之還從存儲器調用其對應的規則樹，該規則樹包括與該鍵的該字符相關聯的先前輸入的字母數字序列的多級層次樹(multi-levelhierarchicaltree)。如果所顯示的字符不是所期望的字符，則在用戶通過按下相同的鍵(即，多次敲擊)來作出請求之後，顯示與該鍵相關聯的另一個字符。用戶可通過等待一默認時間段或通過選擇一個不同的鍵來選擇該字符，隨後還從存儲器調用其對應的規則樹，該規則樹同樣包括與該鍵的該字符相關聯的先前輸入的字母數字序列的多級層次樹。如果所顯示的字符不是所期望的字符，則根據用戶的請求，順序顯示與該鍵相關聯的其它字符，直到選擇了所期望的字符為止(如果一個鍵具有與其相關聯的三個字符，則最多三次，如果是四字符鍵，則最多四次，等等)。從而選擇了字符l。然後，在輸入用於選擇所期望的字符2的下一個鍵之後，再次分析規則樹，以基於先前輸入的字符1來預測字符2。類似地，在輸入用於選擇所期望的字符3的下一個鍵之後，仍然再次分析規則樹，以基於先前輸入的字符l和字符2來預測字符3。重複這個過程，直到期望詞的所有字符都基於前面配置的先前字符數量(即，至少一個，優選兩個，更優選三個)被預測並被顯示以供選擇為止。只要選擇了先前沒顯示過的字符，就修改規則樹以將該字符包括作為可能的選擇。從而，隨著更多字符被選擇，規則樹被動態地建立。而且，與所顯示字符基於先前選擇的一個或多個字符而被選擇的次數相對應的遞增計數器(incrementcounter)被用於對所顯示字符進行加權，從而將其顯示在也基於相同的先前所選擇的一個或多個字符而被選擇的計數較少的其它字符之上。一旦選擇了詞並輸入空格，通過從存儲器調用與對應於下一個被按下的鍵的第一字符規則列表相關聯的規則樹而重複該方法。重要的是，規則樹可以基於先前輸入的一個或多個字母數字字符序列，所述序列基於存儲在存儲器中的每次使用來動態"建立"規則樹。因此，規則樹基於實際的使用而形成，並且不由語言學規則來指定或由所存儲的字典來提示。而且，因為計數器用來根據先前選擇的一個或多個字符(即，l個、優選2個或更優選3個先前選擇的字符)來加權字符，因此預測期望字符的可能性同樣可應用於首字母縮寫詞、縮略語、科學詞彙等等，並且用於附加的目的，即快速適應使用不同詞彙、語言或具有不同寫作風格的不同用戶。本發明的設備和方法可與具有一個或多個鍵的任何布局的任何鍵區一起使用，其中所述一個或多個鍵具有一個或多個與其相關聯的字符，並且特別地，不限於與DTMF鍵區一起使用。而且，本發明的設備和方法可與任何語言一起使用，所述語言包括可包含與鍵區的特定鍵相關聯的一種或多種符號的語言，諸如日語。出於說明的目的，簡化的根據本發明的預測字符的例子如下根據先前輸入的詞"Mississippi"，建立隨後的規則樹(每個方框的上部表示字符，方框的下部表示在兩個先前輸入的字符之後的字符的遞增計數)和第一字符規則列表formulaseeoriginaldocumentpage10由於系統已經見到詞Mississippi並為它創建了如上所示的規則樹，下次當用戶試圖輸入Mississippi時，預測將如下進行給定鍵映射鍵l=A，B，C鍵2=D，E，F鍵3=G，H，I鍵4=J，K，L鍵5=M，N，O鍵6=P，Q，R鍵7=S，T，U鍵8=V，W，X鍵9=Y,Z鍵序列5，3，7，7，3，7，7，3，6，6和3將基於相應的兩個先前輸入的字符進行如下預測按下的鍵先前的字符所用的預測規則給出的預測正確/錯誤5=M，N，O*M:1'M'正確3=G，H，I"M"M->IT正確7=S，T，U"MI"MI->S,S'正確7=S，T，U"mIS"IS->S,s'正確3=G，H，I"miSS"SS->IT正確7=S，T，U"misSI"SI->s,S'正確7=S，T，U"missIS"IS>s,s'正確3=G，H，I"missiSS"SS>IT正確6=P，Q，R"missisSI"SI->P,p,正確6=P，Q，R"mississIP"IP->p,p,正確3=G，H，I"mississiPP"pp->IT正確作為對照，沒有本發明的預測規則帶來的好處時，如果用戶試圖使用傳統的多次敲擊來輸入"Mississippi"，則發生下面的情況tableseeoriginaldocumentpage12系統流程；圖3是一個流程圖，更詳細地描述向存儲器提交規則的功能；圖4是確定截止(cutoff)權重計算的功能的流程圖；圖5是一個流程圖，說明當使擊鍵通過系統時，本發明的方法在高層的操作；圖6是一個流程圖，更詳細地描述第一字符預測的功能；圖7是一個流程圖，更詳細地描述查找次優預測的功能；圖8是一個流程圖，更詳細地描述在第一字符規則列表中查找預測的功能；圖7是一個流程圖，更詳細地描述查找次優預測的功能；圖8是一個流程圖，更詳細地描述在第一字符規則列表中查找預測的功能；圖9是一個流程圖，更詳細地描述在規則樹中查找預測或規則的功能；圖10是一個流程圖，更詳細地描述當所有字符中的一個或多個不能被預測時，以字母順序填充任何餘下的字符的功能；圖ll是一個流程圖，更詳細地描述在沒有發生觸發事件的情況下更新第一字符規則列表的功能；圖12是在沒有發生觸發事件的情況下更新規則樹的步驟的流程在所有附圖中，相似的參考標記表示相似的部分。具體實施例方式圖i是本發明的文本預測機制io的框圖，其中由可操作地耦接到非易失性存儲器C和隨機存取存儲器D的處理單元B來處理對模糊鍵區A(將多於一個字符分配給一個或多個鍵的鍵區)的鍵的每次按壓。然後，通過圖形用戶界面E來顯示該預測。圖2是一個流程圖，示出實現本發明的方法的電腦程式的高層系統流程。程序從等待狀態l開始，等待觸發事件2，該事件優選包括每個詞或消息的結束，但可替換地可以是每次擊鍵，或者是對於採用了本發明的系統最為合適的任何事件。觸發事件2發生之後，將事件計數器3遞增，以記住系統已經對規則系統執行事件/更新的次數。事件計數器3被用來確定何時將規則更新保存到非易失性存儲器C。但是，雖然非易失性存儲器C通常較慢，更快的非易失性存儲器C將允許將更新直接保存到存儲器，從而不需要事件計數器3。在遞增事件計數器3之後，動態加權的第一字符規則列表被更新4，然後動態加權的規則樹被更新5。完成這些更新4和5後，確定6是否已經發生了足夠的觸發事件2，以便批准把更新4和5提交7給非易失性存儲器C。注意，在執行提交7之前所需要的觸發事件2的數量可以根據應用來調整。例如，如果CPU時間非常寶貴，則事件計數器3可被預置為僅在發生了大量的觸發事件2之後才提交7。與此相反，如果系統沒有大的平均"可使用時間(uptime)"，則較少量的觸發事件會使得規則4和5被提交7。如果上述兩種情況都存在，則可在僅僅少量觸發事件2之後進行第一少量提交7，並且當系統停留在加電狀態時，可在觸發事件2的數量日益增多時進行提交7以幫助節約CPU周期。如果已經發生了足夠的觸發事件2，則規則4和5被提交7給非易失性存儲器C，然後事件計數器被復位8，流程重新進入等待狀態1。如果沒有發生足夠的觸發事件，則流程直接進入等待狀態1，而無需將規則4和5提交7給非易失性存儲器C。圖3是一個流程圖，更詳細地描述向非易失性存儲器C提交7圖2的規則4和5的功能。第一步是精確複製71第一字符規則列表4。注意，不需要壓縮其大小，因為其大小僅為26個字節(基於英語字母表的26個字母)。但是要注意，因為每個字符需要一個字節的存儲空間，更大的字母表將需要成比例的更多存儲空間，因而可能希望壓縮。存儲規則樹5的第一步是確定在什麼截止72處不應當存儲規則144和5。優選在每次存儲規則樹時重新計算截止72，從而使計數器72能夠適用於規則樹5可能處於的任何狀態。例如，如果非易失性存儲器C受到限制，則優選在存儲之前削減(prune)規則樹。更具體地，將截止72與規則的當前值相比較。如果該值小於截止72，則不存儲規則，也不存儲任何其子規則，因為它們的值總是比其父規則的要小。一旦確定了截止72，就在規則樹5中的第一節點或根節點73處開始，將根節點的值與截止作比較74以確定根節點的值是否大於截止72。如果大於，則將規則的值規格化75，以使其適合於非易失性存儲器C。只有當在樹中找到的最大規則值在不捨去其最高有效比特時就不完全適合於非易失性存儲器C時，才優選地進行規格化75。規格化75規則的值而達到的最大值是可根據有多少空間可用而配置的。例如，在優選實施例的一個實施方式中，所有的值都被規格化成最大值為512或9比特。該最大值將限制規則可與之比較的粒度(類似於8比特和10比特的模數轉換器之間的差別)。如果使用較小的最大值，如256或128，則較多的規則可由於規格化過程75而具有相同的計數。通過測試優選實施例，似乎具有這樣的最大值是優選的，即最大值為一到兩倍於來自要存儲在非易失性存儲器C中的樹的規則總數。最大值的另一方面是系統適應性。如果最大值較大，則意味著在全新的規則可能克服先前主導的規則之前，該全新的規則必須發生很多次。如果允許系統長時間運行而不進行循環通電(powercycle)的話，這個問題較小。但是，如果期望頻繁的循環通電，並且如果最大值增加過多，則可能沒有足夠的時間使可能"好"的規則艱難地"提升"並且不能得到消減。相反地，如果最大值減小太多，則新規則將會過快地克服先前主導的規則，可能導致系統性能的振蕩。一旦規則已經被規格化75，規則就被插入76到位於非易失性存儲器C中的樹中。這需要簡單的樹遍歷，以及將數據複製到新位置。一旦規則已經被複製76，則進行檢查77，以確定是否還剩有任何需要被存儲的規則。如果是，並且如果有更多的規則，則以深度優先方15式選擇78下一規則。利用該規則，檢查該規則以確定其值是否大於截止74。如果小於截止，則該規則及其全部子規則都被忽略79。循環繼續，直至所有需要存儲的規則都已經被存儲為止。圖4是確定圖3中的截止72的功能的流程圖。截止權重計算72在規則樹自身之外還需要兩個另外的輸入。首先，必須確定當前在樹中的實際規則數量721，以及可存儲在非易失性存儲器中的最大規則數量722。下一步是遍歷規則樹，並臨時規格化每個規則的權重723。規格化計算723優選與在提交規則給非易失性存儲器C時所使用的相同。但是，既然規則已經被規格化，整個樹應當被遍歷以確定在每個權重級別上存在多少規則724，從而生成規則權重的直方圖。簡單的計數器被用於平衡計算，以獲知何時存在足夠的規則以便隨後將臨時計數器初始化為零725。從最大權重開始726(在優選實施例的實施方式中是512)，規則出現的數量及該權重被加到727臨時計數器TCNT，其剛被初始化為零725。如果TCNT中的值不大於可存儲的規則的最大數量728，則過程移到系統中次低的權重729，並再次將其計數加到727臨時計數器中。如果TCNT中的值仍然不大於可存儲的規則的最大數量728，則過程再次移到系統中次低的權重729。一旦超過可存儲的最大數量728，截止權重被設置為在當前權重之上的一個權重7210。雖然這保證不會有多於可容納的規則的規則被寫入非易失性存儲器中，但是這也意味著很可能會有未使用的存儲空間，因為某些在次低權重的規則可能已經適合。如果包括了這些其它規則，則概念上可能提高循環通電中的性能，因為在啟動時將有稍大的規則資料庫。但是，根據對優選實施例的試驗，即使當保證所有可用的存儲空間都被使用時，如果有提高的話，也是非常小的提高。顯然，沒有可覺察的性能提高是由於存儲的最終規則並不幾乎一樣普遍(common)，因此不會使系統的預測能力增加很多。一旦截止權重被確定7210，其被返回7211，從而可被使用。圖5是一個流程圖，說明當使擊鍵通過系統時，本發明的方法在高層的操作。系統啟動於等待狀態，並優選等待直到在任何其它事件發生之前有來自用戶的擊鍵為止51。當接收到擊鍵52時，進行檢查以確定是否發生了更新事件53。在優選實施例中，更新事件是指示要保存或發送消息的擊鍵。但是，在其它實施例中，更新事件可能是根據系統需求的任何其它類型的事件。在優選實施例中，如果事件確實發生了，第一字符規則列表被更新54，並且規則樹55被更新，之後返回到等待狀態55。在其它實施例中，在更新之後，仍可能以另一個方式繼續處理該擊鍵。如果事件沒有發生，進行檢查以確定這是否是一個重複擊鍵(換而言之，用戶連續按了相同的鍵兩次或多次)56。如果這是重複擊鍵，則確定次優的預測57。發生這個主要有兩個原因。第一個原因是原始預測的字符不正確，如同某些時候可能發生的一樣。另一個原因是用戶第二次僅僅是誤按了按鈕。如果擊鍵不是重複鍵，則確定對下一字符的第一預測58。來自步驟57或58的預測被臨時地插入顯示緩存中，以允許用戶看到被預測的內容59。用戶然後確定該預測是否正確。如果用戶喜歡當前預測，則用戶將使該預測510固定，這將使光標移到下一個位置511。注意，光標可能通常具有由於不同的擊鍵或者超時而自動前進的能力(任一情況下，該實現方式與預測系統的功能無關)。在光標已經前進之後，流程返回到等待狀態，直到用戶按下另一個鍵，這時系統重新開始。圖6是一個流程圖，更詳細地描述圖5的第一字符預測58的功能。當執行第一預測58時，系統傳遞被按下的鍵581和已經被輸入到系統中的先前字符(如果有的話)582。首先，進行檢查以確定是否傳遞過任何先前字符583。如果沒有給出先前字符，則過程知道這是新詞的開始，並且查找585在第一字符規則列表中的預測。但是，如果有至少一個先前字符，則規則樹被用來查找584預測。兩個查找584和585都返回可變大小的列表，其包含從0到"每個鍵映射的最多字符"。如果沒有字符返回，則意味著當前不存在與先前字符和被按下的鍵有關的規則，或者如果詞中的第一字符返回，則意味著不存在與剛按下的鍵有關的規則。返回多於一個字符的原因是，系統必須以對於該情況最佳的可能順序對所有被映射到鍵的字符進行排序(order)。例如，一個鍵與"A"、"B，，和"C，，映射，則對這三個字符有六種可能的排序。有些情況下，A、B、C是最可能的順序，而在其它情況下，C、A、B會是最佳的順序。規則樹將基於存在的規則確定可能的一切規則。在某些情況下，因為缺乏所需的規則，可能僅僅能夠預測第一字符，但是在其它情況下，如果它具有所需的規則，則能夠將所有這三個字符排序。一旦規則樹作出了預測，就檢查以確定是否所有映射到鍵的字符586都被包括在預測中。如果不能預測所有字符，則以字母順序填充67剩下的字符。注意，在優選實施例中，嘗試過更智能的排序，但是沒有獲得性能的顯著提高(<0.5%)，周此認為去除這類更智能的排序所需要的額外複雜度是更有價值的。系統包括附加的試探法，以幫助猜測用戶在擊鍵時是否希望輸入大寫、小寫或數字。因此，系統將對預測排序，從而減少為了達到所期望的字母大小寫或數字所需要的擊鍵次數588。試探法簡單地記住輸入的上個字符的大小寫或者上個字符是否為數字，於是系統保持該大小寫直到用戶切換大小寫為止，這時，系統將記住新的大小寫。例如，如果先前字符是大寫字母，則預測的排序可能是這樣大寫字符，然後是數字，然後是小寫字符。如果先前字符是小寫字母，則排序可能是小寫字母，然後是數字，然後是大寫字母。如果先前字符是數字，則排序可能是數字，然後是大寫字母，然後是小寫字母。一旦完成預測(在優選實施例中是7個字符，大寫字母、數字和小寫字母)，則預測被存儲，使得接下來對GetNextPrediction(獲取下一預測)步驟的調用會非常有效，沒有處理延遲589。當前預測在存儲的預測列表中的位置優選地被初始化為零，以指示將要返回第一預測5810。最後，返回單個字符預測5811。圖7是一個流程圖，更詳細地描述查找圖6的次優預測57的功能。第一步是遞增用於指示在預測列表中的位置的計數器571。預測列表包含擊鍵可能代表的大寫和小寫字母以及數字。因為預測將會"首尾相接(wraparound)"，因此檢查以確定是否已經到達列表結尾572。如果是，則位置計數器被設置回到零，使得流程可以循環回去查找列表573。下一步是基於當前的計數器值檢索預測574,並最終返回該值575。圖8是一個流程圖，更詳細地描述在圖6的第一字符規則列表585中查找預測的功能。查找第一字符從其是被按下的鍵的單個輸入開始5851。搜索整個第一字符規則，直至找到所有關於擊鍵的規則5852。在優選實施例中，可找到最多三個規則，一個用於每個映射到給定鍵的字母。接下來，將基於其權重而找到的規則進行分類(sort)5853。最後，返回分類後的預測和找到的規則的數量5854和5855。圖9是一個流程圖，更詳細地描述查找規則以進行圖6的預測584的功能。規則樹查找64從其是被按下的鍵的兩個輸入和已經輸入的詞的先前字符5841和5842開始。在規則樹的根節點處開始查找5843。注意，規則樹的每個節點實際上是一個規則列表，其每個規則能夠擁有子節點，因此樹的分支因子可以非常大(即，跟預測字母表中的字符數目一樣大)。通過移過在當前(第一)節點上的列表，找到給出的先前字符中的第一個5854。例如，如果傳遞字符串"thei",則要查找的字符是"t"。下一步是檢查是否確實已經找到該字符5845。如果沒有找到該字符，則先前字符串向左移動一個位置，給出一個新的首字母58413。例如，移位後，初始字符串"thei"將看起來像"hei"。在繼續之前，檢查以確定是否還有先前字符要處理。在這個例子中，仍然剩下有3個字符58414。利用新的先前字符串，在當前節點中再次查找第一宇符(例如"h")5844和5845。如果這次找到了規則(例如用於"h"的規則)，則檢查以確定其是否具有子節點。換而言之，在樹中是否有從該規則19通往的另一層5846如果沒有，則不能找到在下一層的規則(例如，不能找到用於"e"的規則，以及用於"i"的位於第3層的規則)。這意味著系統不得不認為對於該字母組合，尚沒有規則被添加到樹中。同樣，如果不存在另一層，意味著因而必須使用較短的先前字符串。在當前的例子中，這將意味著先前字符串現在看起來像"ei"。但是，如果在樹中有從第一層的第一規則(例如，"h"規則)通往的另一層。接下來，確定是否還有任何先前字符要處理5874。在當前例子中有，所以當前層指針移動到樹中的下一層(即，"h"規則的子節點)5848。在樹中的下一層，在當前層搜索下一先前字符(例如"e")。如果存在的話，重複所述檢查過程。如果不能找到，則意味著該深度第一搜索路徑又是死路，使得我們將我們先前的字符串減短1,然後再次搜索。如果另一方面，在當前層找到了它(例如"e"),則進行檢查以確定樹中是否還有從該(例如"e")規則通往的另一層。如果有，則再次搜索先前字符串中的下一字符(例如"i")。將同樣的過程應用於這個字符，如同所有先前字符一樣。假設找到了用於字符(例如，"i，，)的規則，則過程返回步驟5845。還記得，在我們當前的例子中，字母"i"是我們原始先前字符串"thei"中的最後一個字母，則下一步再次確定樹中是否還有從"i，，通往的另一層5856。如果沒有，則再次減短先前字符串。但是，如果有另一層，則再次檢查以確定在先前字符串中是否有另一個字符。在當前例子中，不再有其餘的字符，因此檢查下一層以確定基於給定的按鍵輸入來預測什麼字符58410。例如，假設用戶試圖輸入詞"their",並且字母"p、q和r"映射到鍵6。基於該擊鍵和字母表的鍵映射，將在樹中的下一層查找字母"p、q和r，，的規則。進一步假設找到以下(規則，值)對(r，10)、(p，3)和(q，6)。在這種情況下，"r"規則將是所找到的"最強"規則，因此將是預測的第一個字母。最強規則可以定義為利用最大數量的先前字符找到的、並在與其相同節點找到的所有規則中具有最大值的規則。如果存在多於一個規則，則優選地利用最先出現的最大值將規則分類58411。如果存在一些規則，應當檢查以確定是否已經找到了所有的規則58412。根據系統的鍵映射，這可能意味著每個鍵可能具有最多每個鍵2、3、4或者更多字符。為了使最可靠的預測成為可能，優選應當找到所有規則。因為目前只找到了最多(本例中是3)規則中的一個，因此處理流程循環回到58413以再次減少所查找的先前字符的數量，假設還有任何剩餘字符的話。如果還剩有先前字符，則利用較少的先前字符作為輸入而找到的所有規則與第一次找到的規則相比將總是第二預測。換而言之，無論其具有什麼值，它們將被分類以使得他們永遠不能佔據預測列表的最前面的位置。一旦先前字符被耗盡，或者一旦已經找到對於該次擊鍵的最大數量的預測，就將找到的預測和預測的數量返回58415。圖10是一個流程圖，更詳細地描述如果不能預測所有字符，則以字母表順序來填充字符的功能。更具體地，如果預測樹不能提供完全預測，則利用餘下的映射到被按下的鍵的字母來填充預測的空位。為此，提供了兩個輸入5871和5872，其是被按下的鍵以及被預測的字符的數量。例如，如果最多有三個字符映射到每個鍵，而且僅能預測這些字符中的一個，則將需要填充餘下的兩個字符。通過測試前面提到的優選實施例，確定主要的性能提高來源於對預測列表中第一字符的更準確預測。還確定，當使用填充餘下的預測的"智能"方法時，系統性能僅有少量提高。提高足夠小以至於用戶不能察覺提高的預測性能，也似乎不能克服執行"智能"填充操作所需的開銷。考慮到這一點，優選地認為所有餘下的字符被以字母表順序來"預測"，並且相應地被填充5873。一旦預測列表被填滿，流程將其返回以^吏其可被使用5874。圖11是一個流程圖，更詳細地說明更新54第一字符規則列表的功能。更具體地，第一字符規則列表的更新是一個僅僅需要輸入包含至少一個字符的字符串541的過程。系統能夠處理任何無格式的字符串。換而言之，預測中未使用的字符可毫無問題地出現在字符串中。在該優選實施例中，如果系統遇到一個預測中未使用的字符，則將其解釋為空白和詞中斷(wordbreak)。從字符串中的第一個字符開始542，進行檢查以確定這是否是有效的預測字母字符543。如果是，則遞增546在第一字符規則列表中的該字符權重/值。下一步是找到下一個詞的開始，以便找到這個詞的首字母。每次進行一個字符，因為既不知道當前詞何時結束，也不知道下一個詞從哪裡開始。因此，首先，流程移到下一個字符547，並進行檢查以確定其是否是有效的預測字母字符548。如果是，則進行檢查以確定字符串中是否有字符剩下549。如果沒有，則過程完成，但是如果還有至少一個存在，過程繼續移到每個隨後的字符，檢查它們是否是有效的預測字母字符。如果發現一個字符不是有效的預測字母字符，則在步驟544對更多字符進行檢查。如果還有字符剩下，則有序確定下一個字符545。如果這個新的字符不是有效的預測字符，繼續對字符進行循環檢測，直到找到下一個有效字符為止。這是用於移過可能出現在詞之間的任何空白的方法。一旦找到下一個有效字符，就在規則列表中再次更新其值，並且過程重新開始，以找到下一個詞的首字母。該過程繼續，直到在原始輸入字符串中沒有字符剩下為止。圖12是一個流程圖，更詳細地說明更新規則樹的功能。規則樹的更新是一個僅僅需要輸入包含至少一個字符的字符串的過程551。該系統能夠處理任何無格式的字符串。換而言之，在預測中未使用的字符可毫無問題地出現在字符串中。在該優選實施例中，如果系統遇到一個預測中未使用的字符，則將其解釋為空白和詞中斷。從字符串中的第一個字符開始552，對第一有效預測字母字符進行線性搜索553。一旦找到有效字符，其就被附加到先前字符列表中554。例如，如果傳遞來的字符串是"Hello，thisisatest."。則先前字符列表現在看起來像"H"。預測系統能夠限制應當用於做出預測的先前字符的最大數量。在該優選實施例的實施方式中，考慮到剩下的系統參數，發現三個先前字符的效果最好，但是為了簡潔起見，這裡的22例子中將僅使用兩個先前字符。進行檢查555以確定先前字符列表的長度是否大於最大值。在我們的例子中，尚未達到該極限，因此過程將在規則樹的根節點開始557，並且進行搜索，看是否能夠找到第一先前字符"H，，558。注意，預測系統優選地對大小寫不敏感，因此所有字符都跟小寫一樣被處理。接下來，進行檢查以確定在當前節點中是否找到了對應的規則559，其中每個節點可以是字符值對或規則的鍊表。例如，假設沒找到字母"H，，，將創建新規則以記住"H"是新詞的首字符這一事實。這通過向該節點的規則列表的末端添加新規則而實現。在添加了規則之後，其值、計數器或權重被設置為等於一5512。這說明該規則僅僅發生了一次。該值也可在以後使用，以便在執行預測時再次與其它規則比較。一旦已經添加了該規則，就進行檢查以確定下一字符是否在預測字母表中5513。如果不在，則先前字符列表被清除5514，因為這意味著當前字已經完成。在清除先前字符列表之後，再次對輸入字符串進行線性搜索，直到找到來自預測字母表的另一個字符為止5515。根據這一點，繼續進行與我們例子中以字母"H"開始的循環相同的循環。假設回到搜索下一個有效字符的例子中，則找到的下一個字符是"e"。這是有效的，因此，將其附加到先前字符列表554，從而產生"He"。進行檢查以確認沒有過多的先前字符正在被檢查555，然後過程在根樹層再次開始以找到剛被添加到樹的"H"規則557和558。一旦找到了559，就進行檢查以確定是否還要使用先前字符5510。在這個例子中，有"e"，因此過程移到下一樹層5511。通過跟隨"H"規則的子指針而到達下一樹節點。這裡，在當前節點上進行搜索以尋找"e"558。在確定該規則不存在559之後，用於"e"的新規則被添加到當前節點的規則列表中，並且其值被設為1。在添加了規則之後，獲取下一個字符的過程繼續進行，引領通過步驟5513和5514。這時，先前字符列表將看起來像"Hel"。如果在步驟555假設最大深度為2，則過程繼續到步驟556,其中消除了先前詞列表的第一個字符，從而提供得到的列表"el"。重複相同的過程，從而在根節點找到規則"e"，並在"e"規則的子節點找到"l"規則。假設兩個規則都已經存在。則過程繼續到步驟5510，其中進行檢查以確定是否還要尋找先前字符。在當前例子中，"l"是最後的先前字符，因此過程移到步驟5516，其中"l，，規則的值增加1。下一步是屏蔽(即，不刪除，只是忽略)先前字符列表中的第一字符5517。為了形象化，假設"*"代表被屏蔽的先前字符，這得到新的先前字符列表"*1"，系統對其進行處理，好像它就是列表"l，，一樣。下一步是檢查在先前字符列表中是否餘下任何未屏蔽的字符5518。在當前例子中，字符"l"仍然未屏蔽，因此流程移到步驟557並在根節點再次搜索現在是第一先前字符的字符557和558。假設在根節點中存在用於"l"的規則，則其被遞增559，5510和5516。下一步是屏蔽第一字符。還記得，當前例子之前的循環具有字符串"el"，其被屏蔽以得到"*1"，這次"l"是第一字符，因此得到字符串"**"5517。進行檢查以確定是否還有任何未屏蔽的字符5518。因為先前字符列表已經完全被屏蔽了，所以流程轉到步驟5519以解除對所有字符的屏蔽，從而將字符串"""變回"el"。重新開始循環，查找下一字符以找到導致"ell"的另一個"l",因為樹深度的限制，"ell"被縮減為"ll"。作出適當的更新，然後下一個新字符"o"得到"llo"，因為樹深度的限制，其被縮減為"lo"。最後，在更新這些之後，檢查下一字符5513，並找到空格字符。因為這不是有效的預測字母字符，流程移到步驟5514，以刪除先前字符列表的全部內容。發生這個，是因為已經找到當前詞的結尾，並且系統已經準備好處理下一個新詞。在步驟5515，繼續搜索下一個有效的預測字母字符，直到找到一個為止。這允許系統處理任意數量的可分隔每個詞的無效或空白字符。整個過程繼續進行，直到原始輸入字符串中的所有字母都被處理了為止。權利要求1.一種用於通過按下簡化鍵鍵區的多字符鍵來預測期望詞的字符的方法，包括以下步驟(1)通過以下動作，訪問與期望詞的第一詞字符相對應的第一字符規則列表選擇具有鍵字符的第一鍵，所述鍵字符是所述期望詞的所述第一詞字符；以預測的順序，每次一個顯示所述第一鍵的所述鍵字符，並當所述鍵字符是所述期望詞的所述第一詞字符時，選擇所顯示的鍵字符作為第一字符鍵；(2)處理包括多級層次規則樹的規則樹，以順序地預測並顯示所述期望詞的後續詞字符，並且允許在所期望的後續詞字符被顯示時對其進行選擇，或者允許通過多次敲擊來選擇新的期望詞字符。2.如權利要求l所述的方法，還包括步驟基於先前選擇由所述規則預測的所述後續詞字符的次數，來動態加權對所述期望詞的所述後續詞字符的每個規則的預測。3，如權利要求2所述的方法，其中所迷動態加權每個規則的步驟包括步驟基於在選擇至少一個緊接在前的詞字符之後先前選擇所述後續詞字符的次數來進行加權。4.如權利要求3所述的方法，其中所述動態加權所述規則樹的步驟包括遞增計數器以加權與在相同的先前被按下的鍵之後的隨後預測相關聯的預測。5.如權利要求2所述的方法，還包括步驟規格化基於所述先前預測正確地預測了所述期望字符的次數而對其它期望字符的隨後預測進行的動態加權。6.如權利要求2所述的方法，還包括步驟從所述規則樹中刪除一個或多個具有最低權重的規則。7.如權利要求l所述的方法，還包括在選擇了每個字符之後，在選擇了期望詞的所有期望字符之後，或者在選擇了多個期望詞的所有期望字符之後，更新所述規則樹。8.如權利要求l所述的方法，其中所述當所述鍵字符是所述期望詞的所述第一詞字符時顯示所述第一鍵的所述鍵字符和選擇所顯示的鍵字符作為所述第一字符鍵的步驟包括步驟基於所述第一字符鍵被選擇的次數來加權所述選擇，然後基於所述加權後的選擇，來預測所述後續第一鍵字符的順序顯示。9.如權利要求8所述的方法，其中所述每次一個顯示與所述鍵相關聯的所有鍵字符的步驟是以預測的順序發生的。10.如權利要求8所述的方法，其中所述預測的順序包括字母順序。全文摘要一種用於基於先前對字符的選擇來預測按下的簡化鍵鍵區的多字符鍵的期望字母數字字符的方法和設備。在使用時動態建立規則樹，以便易於運用於所有語言風格和詞彙，其中所述規則樹定義了基於先前對字符的選擇的、與按下的鍵相關聯的預測。而且，規則樹被加權，以便提高預測期望字符的概率，並迅速適應於具有不同語言風格或詞彙的不同用戶。文檔編號G09G5/00GK101449318SQ200780018140公開日2009年6月3日申請日期2007年3月28日優先權日2006年3月30日發明者J·L·施米德林,W·M·D·卡洪申請人:哈裡公司