[發明專利]用于處理字符流的方法與設備

有效

• 申請號: 200680030295.0
• 申請日: 2006-06-16
• 公開（公告）號: CN101243441A
• 公開（公告）日: 2008-08-13
• 發明（設計）人: R·D·卡梅隆
• 申請（專利權）人: 國際字符股份有限公司
• 主分類號: G06F17/22
• 分類號: G06F17/22
• 代理公司: 上海專利商標事務所有限公司
• 代理人: 李玲

本專利申請涉及根據35USC§119(e)要求其優先權的2005年6月21日提交的美國臨時申請No.60/692,683，該臨時申請的全部內容都被包括于此。

技術領域

本發明的一個或多個實現涉及用于處理字符流的方法與設備

背景技術

文本處理應用用于處理按照特定的字符編碼方案的規約被編碼成字符串或字符流的文本數據。長期以來，很多已開發的文本處理應用都是基于固定長度，單字節的字符編碼方案，例如，ASCII和EBCDIC。此外，涉及各種歐洲語言或非羅馬字母的文本數據的文本處理應用可使用ISO?8859的8位擴展的ASCII的方案之一。另外，一些可供選擇的變長編碼方案被用于中文，日文和韓文的應用。

Unicode正逐漸地被用作可能需要調整和/或組合不同來源的文本的文本處理應用的基礎。Unicode字符集被設計為包括世界各地語言的字符，同時也包括來自用于數學，音樂和其他應用領域的正規符號系統的一些附加的字符。眾所周知，UTF-8，UTF-16和UTF-32分別是基于8位，16位，32位代碼單元的三種基礎的Unicode編碼方案。特別地，UTF-8是每個字符需要一至四個8位代碼單元的一種變長編碼方案；UTF-16是每個字符通常需要單個16位代碼單元的編碼方案(有些不常用的字符需要兩個代碼單元)；以及UTF-32是每個字符需要單個32位代碼單元的定長編碼方案。UTF-16和UTF-32具有一些被稱為UTF-16LE，UTF-16BE，UTF-32LE和UTF-32BE，這取決于代碼單元內的字節排序規約。

盡管Unicode允許應用和來自許多不同資源的字符流間的相互操作，與已往基于8位字符編碼方案的應用相比在處理效率上要付出一定成本。該成本在以為了實現期望的吞吐量所需的額外硬件、執行對特定字符流的應用的額外能耗，和/或一應用完成處理的所用的額外執行時間的形式表現出來時會變得很明顯。

應用還可能要求將數據流的內容根據基于文本的符號系統的詞法和/或者句法的規約結構化。存在很多這樣的規約，范圍從用于各種操作系統的簡單的面向行的結構規約，到用于將計算機程序表示為源語言文本的正規程序語言文法。特別重要的是，XML作為用于編碼文檔和各種數據的一種標準的基于文本的標記語言的使用不斷增加。在每種情況下，強加結構化信息可能會相當程度上增加對相關文本處理應用的資源需求。

一般而言，現有技術的高速文本處理用了順序的一次一個字符(或一次一個字節)的處理，通常用C程序語言來編寫。例如，XML和Unicode串處理的許多現有技術教授了順序字符處理方法的使用。標準計算科學教科書也是這樣處理解析、詞法分析和文本處理應用的。

在現有技術中，有三種用于實現文本處理應用的基本技術。第一種基本技術是使用了迭代循環(例如，while循環)和分支指令(例如，if語句)來執行基于特定的字符或字符類的條件動作的手編實現。第二種基本技術是第一種變形，其中對不同字符或字符類的不同邏輯的分解是通過轉移表來處理的(例如，case語句)。第三種基本技術是將有限狀態機形式的表的使用系統化。有限狀態機實現來源于串處理的標準理論技術；也就是用正則表達式文法來表示字符和詞法語法，以及用有限自動機來識別與這些文法匹配字符串。當狀態的數量和每個狀態潛在字符轉換的數量適度小時有限狀態機技術可以給出有效實現；例如涉及7位位的ASCII處理應用每個狀態需要至多128個條目。然而，基于UTF-16的16位表示的有限狀態機的一次簡單實現都需要每個狀態64,000個條目以上。因此，對于任何復雜的狀態空間，這很快被禁止。

工業標準處理器已演化為8位，16位和32位的體系結構。另外，字符編碼方案已從擴展的ASCII的8位表示演化為16和32位的UTF16和UTF32表示。經過了處理器體系結構和字符編碼方案的這種演化，處理器的性能和一次一字符處理的要求之間有了大致匹配。