JP2000259638A - 記号列処理装置 - Google Patents
記号列処理装置Info
- Publication number
- JP2000259638A JP2000259638A JP11066251A JP6625199A JP2000259638A JP 2000259638 A JP2000259638 A JP 2000259638A JP 11066251 A JP11066251 A JP 11066251A JP 6625199 A JP6625199 A JP 6625199A JP 2000259638 A JP2000259638 A JP 2000259638A
- Authority
- JP
- Japan
- Prior art keywords
- symbol
- symbol string
- context
- unit
- input
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F40/00—Handling natural language data
- G06F40/10—Text processing
- G06F40/12—Use of codes for handling textual entities
- G06F40/123—Storage facilities
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Health & Medical Sciences (AREA)
- Artificial Intelligence (AREA)
- Audiology, Speech & Language Pathology (AREA)
- Computational Linguistics (AREA)
- General Health & Medical Sciences (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Machine Translation (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【課題】 文脈の規模が増大しても文字列索引の記憶量
を比較的少なくすることができる記号列処理装置１を提
供する。 【解決手段】 入力部２には記号列を入力する。バッフ
ァ部３は記号列を記憶する。索引部４は記憶された記号
列の位置番号列を記憶する。検索部５は、入力部２で入
力された記号列の部分記号列についてバッファ部３に記
憶されている記号列中での出現位置を索引部４を用いて
検索する。推定部６は、この検索結果を用いて入力部１
への次入力記号を索引部４に記憶されている位置番号列
の範囲内で推定する。
を比較的少なくすることができる記号列処理装置１を提
供する。 【解決手段】 入力部２には記号列を入力する。バッフ
ァ部３は記号列を記憶する。索引部４は記憶された記号
列の位置番号列を記憶する。検索部５は、入力部２で入
力された記号列の部分記号列についてバッファ部３に記
憶されている記号列中での出現位置を索引部４を用いて
検索する。推定部６は、この検索結果を用いて入力部１
への次入力記号を索引部４に記憶されている位置番号列
の範囲内で推定する。
Description
【０００１】
【発明の属する技術分野】この発明は、記号列中で次に
位置する記号を記号列の文脈から推定する記号列処理装
置に関する。
位置する記号を記号列の文脈から推定する記号列処理装
置に関する。
【０００２】
【従来の技術】テキスト圧縮においてよく用いられる統
計的言語モデルとして、ＰＰＭ（Predict Partial Matc
hing）がある。このＰＰＭには、ＰＰＭ＊と呼ばれる変
種がある（“J.G.Cleary and W.J.Teahan著／Unbounded
length contexts for PPM／Computer Journal,40(2):6
7-75,1997”および“小田祐樹、北研二著／ＰＰＭ＊モ
デルによる日本語単語分割／ＮＬ報告,128(2),1998”参
照）。このＰＰＭ＊は、モデルの次数ｎ（文脈長）に上
限を設けないことを特徴とする。
計的言語モデルとして、ＰＰＭ（Predict Partial Matc
hing）がある。このＰＰＭには、ＰＰＭ＊と呼ばれる変
種がある（“J.G.Cleary and W.J.Teahan著／Unbounded
length contexts for PPM／Computer Journal,40(2):6
7-75,1997”および“小田祐樹、北研二著／ＰＰＭ＊モ
デルによる日本語単語分割／ＮＬ報告,128(2),1998”参
照）。このＰＰＭ＊は、モデルの次数ｎ（文脈長）に上
限を設けないことを特徴とする。
【０００３】ＰＰＭ＊においては、過去の文脈をコンパ
クトに格納し、柔軟かつ高速にそれらを参照および追加
削除できる文字列索引が必要になる。このような文字列
索引としては、従来、trieなどが用いられる。
クトに格納し、柔軟かつ高速にそれらを参照および追加
削除できる文字列索引が必要になる。このような文字列
索引としては、従来、trieなどが用いられる。
【０００４】
【発明が解決しようとする課題】しかし、文字列索引と
してtrieなどを用いた場合は、文脈の規模が増大するに
つれて、記憶量の面で限界があるという不具合がある。
してtrieなどを用いた場合は、文脈の規模が増大するに
つれて、記憶量の面で限界があるという不具合がある。
【０００５】また、従来のＰＰＭ＊は、比較的簡単な文
脈選択の手法を用いており、次に入力される記号の推定
性能は未だ不充分であるという不具合がある。
脈選択の手法を用いており、次に入力される記号の推定
性能は未だ不充分であるという不具合がある。
【０００６】この発明の目的は、文脈の規模が増大して
も文字列索引の記憶量を比較的少なくすることができる
記号列処理装置を提供することである。
も文字列索引の記憶量を比較的少なくすることができる
記号列処理装置を提供することである。
【０００７】この発明の別の目的は、従来より次記号の
推定性能が高い記号列処理装置を提供することである。
推定性能が高い記号列処理装置を提供することである。
【０００８】
【課題を解決するための手段】請求項１に記載の発明
は、記号列を入力する入力部と、記号列を記憶するバッ
ファ部と、この記憶された記号列の位置番号列を記憶す
る索引部と、前記入力部で入力された記号列の部分記号
列について前記バッファ部に記憶されている記号列中で
の出現位置を前記索引部を用いて検索する検索部と、こ
の検索結果を用いて前記入力部への次入力記号を前記索
引部に記憶されている位置番号列の範囲内で推定する推
定部と、を備えている記号列処理装置である。
は、記号列を入力する入力部と、記号列を記憶するバッ
ファ部と、この記憶された記号列の位置番号列を記憶す
る索引部と、前記入力部で入力された記号列の部分記号
列について前記バッファ部に記憶されている記号列中で
の出現位置を前記索引部を用いて検索する検索部と、こ
の検索結果を用いて前記入力部への次入力記号を前記索
引部に記憶されている位置番号列の範囲内で推定する推
定部と、を備えている記号列処理装置である。
【０００９】したがって、索引部はバッファ部に記憶さ
れた記号列の位置番号列を記憶するものであるので、記
憶量が従来より少なくてすむ。
れた記号列の位置番号列を記憶するものであるので、記
憶量が従来より少なくてすむ。
【００１０】請求項２に記載の発明は、請求項１に記載
の記号列処理装置において、前記推定部は、前記次入力
記号の前記推定を行うために文脈を選択するのに際し、
当該記号の直前の記号の前記推定で選択した文脈の情報
を利用するものである。
の記号列処理装置において、前記推定部は、前記次入力
記号の前記推定を行うために文脈を選択するのに際し、
当該記号の直前の記号の前記推定で選択した文脈の情報
を利用するものである。
【００１１】したがって、ある記号の推定を行うために
文脈を選択するのに際し、当該記号の直前の記号の推定
で選択した文脈の情報を利用することにより、従来より
次記号の推定性能を高めることができる。
文脈を選択するのに際し、当該記号の直前の記号の推定
で選択した文脈の情報を利用することにより、従来より
次記号の推定性能を高めることができる。
【００１２】請求項３に記載の発明は、請求項１に記載
の記号列処理装置において、前記推定部は、前記入力部
で入力された記号列が日本語文字であるときは、日本語
文字の字種情報を用いて前記推定のための文脈を選択す
るものである。
の記号列処理装置において、前記推定部は、前記入力部
で入力された記号列が日本語文字であるときは、日本語
文字の字種情報を用いて前記推定のための文脈を選択す
るものである。
【００１３】したがって、入力部で入力された記号列が
日本語文字であるときは、日本語文字の字種情報を用い
て次入力記号の推定のための文脈を選択することによ
り、従来より次記号の推定性能を高めることができる。
日本語文字であるときは、日本語文字の字種情報を用い
て次入力記号の推定のための文脈を選択することによ
り、従来より次記号の推定性能を高めることができる。
【００１４】
【発明の実施の形態】（ＰＰＭ＊について）ＰＰＭ＊に
ついて説明する。有限のアルファベット集合をＡとし、
Ａの要素を記号と呼ぶ。ＰＰＭ＊を用いた言語モデルへ
の入力は記号列であり、ある時点までの入力を、ｘo，
ｘ1，…，ｘi-1とする。ここで各ｘk（ｋ＝０，１，
…，ｉ−１）は記号を表わす。ＰＰＭ＊などのn-gramモ
デルにおいて中心になるのは、次の条件付確率の推定で
ある。
ついて説明する。有限のアルファベット集合をＡとし、
Ａの要素を記号と呼ぶ。ＰＰＭ＊を用いた言語モデルへ
の入力は記号列であり、ある時点までの入力を、ｘo，
ｘ1，…，ｘi-1とする。ここで各ｘk（ｋ＝０，１，
…，ｉ−１）は記号を表わす。ＰＰＭ＊などのn-gramモ
デルにおいて中心になるのは、次の条件付確率の推定で
ある。
【００１５】 Ｐ（ｘi｜ｘo，ｘ1，…，ｘi-1） … （１） 式において、ｘiは次の入力として予測される記号であ
り、Σxi ∈ AＰ（ｘi｜ｘo，ｘ1，…，ｘi-1）＝１が要
請される。
り、Σxi ∈ AＰ（ｘi｜ｘo，ｘ1，…，ｘi-1）＝１が要
請される。
【００１６】長さｎの記号列ｃnおよびｃnの直後に記号
ｘが出現する頻度を与える関数Ｃn（ｘ）との対を要素
とする集合Ｃ（文脈集合という）を用意する。このと
き、ｃ nをｎ次の文脈と呼ぶ。上記の確率を推定するた
めに文脈集合Ｃの要素と条件部の記号列を右端を起点と
して部分マッチするｃn（ｎ＝−１，０，１，２，…，
ｍ）を取り出す。これらの要素からなる集合を一致文脈
集合と呼ぶ。０次の文脈は空列であり、uni-gramに相当
する。また仮想的な文脈として−１次の文脈を設け、０
次の文脈の直後に出現しなかった記号（未知記号）に対
する文脈として機能させる。０次および−１次の文脈は
任意の記号列と部分マッチするものとする。
ｘが出現する頻度を与える関数Ｃn（ｘ）との対を要素
とする集合Ｃ（文脈集合という）を用意する。このと
き、ｃ nをｎ次の文脈と呼ぶ。上記の確率を推定するた
めに文脈集合Ｃの要素と条件部の記号列を右端を起点と
して部分マッチするｃn（ｎ＝−１，０，１，２，…，
ｍ）を取り出す。これらの要素からなる集合を一致文脈
集合と呼ぶ。０次の文脈は空列であり、uni-gramに相当
する。また仮想的な文脈として−１次の文脈を設け、０
次の文脈の直後に出現しなかった記号（未知記号）に対
する文脈として機能させる。０次および−１次の文脈は
任意の記号列と部分マッチするものとする。
【００１７】一致文脈集合の要素のうち、最大次数ｍを
もつ文脈ｃmの頻度関数を用い、以下のようにして前記
確率を推定する。
もつ文脈ｃmの頻度関数を用い、以下のようにして前記
確率を推定する。
【００１８】 ｐm＝ｐ（ｘi｜ｘo，ｘ1，…，ｘi-1）＝ｃm（ｘi）／（Ｃm＋ｔ）…（２） ただし、Ｃm＝Σx ∈ Aｃm（ｘ）であり、ｔはｃm（ｘ）
＞０となる記号の異なり数である。前記確率値が０のと
きは文脈ｃmにとってｘiは未知であったということに相
当する。文脈ｃmにおける未知記号全体に対しては、次
のエスケープ確率を割り当てる。
＞０となる記号の異なり数である。前記確率値が０のと
きは文脈ｃmにとってｘiは未知であったということに相
当する。文脈ｃmにおける未知記号全体に対しては、次
のエスケープ確率を割り当てる。
【００１９】 ｅm＝ｔ／（Ｃm＋ｔ） …（３） 前記のエスケープ確率は未知記号全体に対するものであ
るから、個々の未知記号に対する確率は、次に大きい次
数ｍ´の文脈を用いて得られた確率との積をとることに
より配分される。
るから、個々の未知記号に対する確率は、次に大きい次
数ｍ´の文脈を用いて得られた確率との積をとることに
より配分される。
【００２０】（suffix arrayについて）この発明の実施
の形態では、ＰＰＭ＊に対して、従来のtrieなどに代え
て、suffix arrayを用いる。そこで、以下ではsuffix a
rrayについて説明する。
の形態では、ＰＰＭ＊に対して、従来のtrieなどに代え
て、suffix arrayを用いる。そこで、以下ではsuffix a
rrayについて説明する。
【００２１】長さＮの文字列をａ0，ａ1，…，ａN-1で
表わす。ここで各ａiは、アルファベットの有限集合Σ
の要素であり、文字と呼ぶ。|Σ|によりアルファベット
の総数を表わす。文字には固有の文字値が定義されてお
り、この文字値に基づいて文字列間にはいわゆる辞書順
＜，＝，＞が定義される。テキストＴ＝ａ0，ａ1，…，
ａN-1に対し文字列Ｓｉ＝ａi，ａi+1，…，ａN-1をテキ
ストＴの先頭からｉ番目の文字位置から始まるsuffixと
呼ぶ。この文字位置ｉをポインタと呼ぶ。suffixarray
はすべてのsuffixを辞書順に並べて得られる長さｎのポ
インタ列Ａ＝ｐ0，ｐ1，…，ｐN-1である。すなわち、s
uffix間の辞書順はＳp0＜Ｓp1＜…＜ＳpN -1となる。
表わす。ここで各ａiは、アルファベットの有限集合Σ
の要素であり、文字と呼ぶ。|Σ|によりアルファベット
の総数を表わす。文字には固有の文字値が定義されてお
り、この文字値に基づいて文字列間にはいわゆる辞書順
＜，＝，＞が定義される。テキストＴ＝ａ0，ａ1，…，
ａN-1に対し文字列Ｓｉ＝ａi，ａi+1，…，ａN-1をテキ
ストＴの先頭からｉ番目の文字位置から始まるsuffixと
呼ぶ。この文字位置ｉをポインタと呼ぶ。suffixarray
はすべてのsuffixを辞書順に並べて得られる長さｎのポ
インタ列Ａ＝ｐ0，ｐ1，…，ｐN-1である。すなわち、s
uffix間の辞書順はＳp0＜Ｓp1＜…＜ＳpN -1となる。
【００２２】文字列の検索にはsuffix arrayを介してテ
キスト中を二分探索することで行われる。
キスト中を二分探索することで行われる。
【００２３】また、suffix間の辞書順を確定するために
アルファベットに含まれない仮想文字（例えば＄）をテ
キストの末に加える。“＄”の文字値としては最小値の
０を想定する。さらに、文字列およびポインタ列を表現
するデータ構造として配列を用いる。図1にテキスト
“ＢＡＮＡＮＡ”の配列（ａ）と、そのsuffix arrayの
例（ｂ）を示す。
アルファベットに含まれない仮想文字（例えば＄）をテ
キストの末に加える。“＄”の文字値としては最小値の
０を想定する。さらに、文字列およびポインタ列を表現
するデータ構造として配列を用いる。図1にテキスト
“ＢＡＮＡＮＡ”の配列（ａ）と、そのsuffix arrayの
例（ｂ）を示す。
【００２４】（記号列処理装置について）次に、この発
明の実施の一形態である記号列処理装置について説明す
る。図２は、この記号列処理装置１の機能ブロック図で
ある。
明の実施の一形態である記号列処理装置について説明す
る。図２は、この記号列処理装置１の機能ブロック図で
ある。
【００２５】記号列処理装置１は文字列Ｉ＝ｘo，ｘ1，
…，ｘn中の各位置で、次に位置する文字の生起確率を
求めるものである。入力部２には文字列Ｉ＝ｘo，ｘ1，
…，ｘnが入力され、バッファ部３に記憶される。
…，ｘn中の各位置で、次に位置する文字の生起確率を
求めるものである。入力部２には文字列Ｉ＝ｘo，ｘ1，
…，ｘnが入力され、バッファ部３に記憶される。
【００２６】索引部４は、バッファ部３に記憶されたコ
ーパスを予めリバース（反転）したものに対してsuffix
arrayＳを生成して記憶する。コーパス中の文字数をＮ
とすると、Ｓは長さＮの整数配列、各要素Ｓ[i]の値は
コーパス中の文字位置であり、その位置を起点とするsu
ffixに一対一対応する。配列Ｓの要素は対応するsuffix
をキーとして辞書順にソートされている。検索キーとな
る文字列に対し配列Ｓを介してコーパスを二分探索する
ことで、文字列のコーパス中の全出現位置を配列Ｓのあ
る連続領域Ｓ[i,j]＝Ｓ[i],Ｓ[i＋1]，…，Ｓ[j]上に得
る。
ーパスを予めリバース（反転）したものに対してsuffix
arrayＳを生成して記憶する。コーパス中の文字数をＮ
とすると、Ｓは長さＮの整数配列、各要素Ｓ[i]の値は
コーパス中の文字位置であり、その位置を起点とするsu
ffixに一対一対応する。配列Ｓの要素は対応するsuffix
をキーとして辞書順にソートされている。検索キーとな
る文字列に対し配列Ｓを介してコーパスを二分探索する
ことで、文字列のコーパス中の全出現位置を配列Ｓのあ
る連続領域Ｓ[i,j]＝Ｓ[i],Ｓ[i＋1]，…，Ｓ[j]上に得
る。
【００２７】検索部５および推定部６は、次のステップ
１〜６に示す、suffix arrayを用いたＰＰＭ＊の動作ア
ルゴリズムを実行する。すなわち、入力部２に入力され
た文字列Ｉ＝ｘo，ｘ1，…，ｘnの各位置ｉ＝０，１，
…，ｎにおいて次のステップ１〜６の処理を行う。
１〜６に示す、suffix arrayを用いたＰＰＭ＊の動作ア
ルゴリズムを実行する。すなわち、入力部２に入力され
た文字列Ｉ＝ｘo，ｘ1，…，ｘnの各位置ｉ＝０，１，
…，ｎにおいて次のステップ１〜６の処理を行う。
【００２８】ステップ１： Ｌ←ｘi-1，ｘi-2，…，ｘ2，ｘ1，ｘ0
【００２９】ステップ２：Ｌをキーとしてsuffix array
によりコーパスを２分探索し、最長一致文字列ｃ＝ｘ
i-1，ｘi-2，…，ｘmを求める。ｃは次数ｎの文脈であ
る。
によりコーパスを２分探索し、最長一致文字列ｃ＝ｘ
i-1，ｘi-2，…，ｘmを求める。ｃは次数ｎの文脈であ
る。
【００３０】ステップ３：文脈ｃのコーパス中の全出現
位置は、suffix arrayＳ上のある連続領域Ｒに格納され
ている。この領域を再び２分探索法により求める。得ら
れた領域のサイズは次数ｍの文脈Ｃの出現頻度であり、
Ｃmと表現する。
位置は、suffix arrayＳ上のある連続領域Ｒに格納され
ている。この領域を再び２分探索法により求める。得ら
れた領域のサイズは次数ｍの文脈Ｃの出現頻度であり、
Ｃmと表現する。
【００３１】以上のステップ１〜３の処理は検索部５に
おいて実行する。
おいて実行する。
【００３２】ステップ４：領域Ｒ中の各配列要素Ｓ[i]
について、コーパス中の先頭からＳ[i]−１の位置にあ
る文字ｘkを検索し、その異なり数ｔを求める。また、
ｘi＝ｘ kが出現した場合はその頻度も求める。この値は
前記した頻度関数ｃm（ｘi）の値に相当する。
について、コーパス中の先頭からＳ[i]−１の位置にあ
る文字ｘkを検索し、その異なり数ｔを求める。また、
ｘi＝ｘ kが出現した場合はその頻度も求める。この値は
前記した頻度関数ｃm（ｘi）の値に相当する。
【００３３】ステップ５：ｃm（ｘi）＞０ならば、前記
（２）式の確率ｐmを返して終了する。
（２）式の確率ｐmを返して終了する。
【００３４】ステップ６：そうでなければ、 Ｌ←ｘi-1，ｘi-2，…，ｘm-1 のように次数をひとつ下げて前記ステップ２に戻り確率
ｐm-1を求める。そしてｅm×ｐm-1を返して終了する。
このエスケープ確率ｅmは前記（３）式で与えられる。
ｐm-1を求める。そしてｅm×ｐm-1を返して終了する。
このエスケープ確率ｅmは前記（３）式で与えられる。
【００３５】以上のステップ４〜６の処理は推定部６に
おいて実行する。
おいて実行する。
【００３６】前記の再帰的なエスケープ処理（back-of
f）は、次文字ｘiの出現がコーパス中で得られるまで行
う。次数０（つまりuni-gram）でも得られない未知文字
に対しては次数−１の文脈として確率ｐ-1＝１／|Ａ|を
与えて停止する。ここで、|Ａ|はアルファベットサイズ
である。
f）は、次文字ｘiの出現がコーパス中で得られるまで行
う。次数０（つまりuni-gram）でも得られない未知文字
に対しては次数−１の文脈として確率ｐ-1＝１／|Ａ|を
与えて停止する。ここで、|Ａ|はアルファベットサイズ
である。
【００３７】（文脈選択の手法について）ＰＰＭでは次
数が、ある値を過ぎて高くなるほど逆に性能が低下す
る。つまり、高次になるほど確率を推定できる文字の範
囲が少なくなるためエスケープが頻繁に起きる。そして
エスケープ確率の推定の粗さによる性能低下が顕著にな
る。Clearyらによる決定性文脈処理の導入は、この問題
を軽減はするが解消はしてくれない。そこで、次文字を
推定する際の性能を向上させるために、記号列処理装置
１において、次に説明する２つの手法、手法１、手法２
を用いる。
数が、ある値を過ぎて高くなるほど逆に性能が低下す
る。つまり、高次になるほど確率を推定できる文字の範
囲が少なくなるためエスケープが頻繁に起きる。そして
エスケープ確率の推定の粗さによる性能低下が顕著にな
る。Clearyらによる決定性文脈処理の導入は、この問題
を軽減はするが解消はしてくれない。そこで、次文字を
推定する際の性能を向上させるために、記号列処理装置
１において、次に説明する２つの手法、手法１、手法２
を用いる。
【００３８】一、手法１について ある文字の生起確率を推定するための文脈を選択する際
に、その当該文字の直前の文字の生起確率の推定で選択
した文脈の情報を利用する手法である。具体的には、次
に用いる文脈長の上限をその直前に用いた文脈長の＋１
とする。この手法１により、選択された文脈の左端が単
語の途中で終わる場合が減少する。
に、その当該文字の直前の文字の生起確率の推定で選択
した文脈の情報を利用する手法である。具体的には、次
に用いる文脈長の上限をその直前に用いた文脈長の＋１
とする。この手法１により、選択された文脈の左端が単
語の途中で終わる場合が減少する。
【００３９】二、手法２について 文脈選択において、潜在的にエスケープの可能性が高い
状況では高次文脈の選択を抑制する手法である。そのた
めに、日本語文字の字種情報を利用する。具体的には、
次に用いる文脈長の上限を、現在の文脈の右端が記号類
の場合は１、平仮名の場合は３とする。
状況では高次文脈の選択を抑制する手法である。そのた
めに、日本語文字の字種情報を利用する。具体的には、
次に用いる文脈長の上限を、現在の文脈の右端が記号類
の場合は１、平仮名の場合は３とする。
【００４０】前記手法１，２を決定性処理とともに導入
したＰＰＭ＊を、ここではＰＰＭ＋＋と呼ぶことにす
る。図３のグラフは、ＰＰＭ、ＰＰＭ＊、ＰＰＭ＋＋の
各々について、文脈次数に対する性能の高低（ここで
は、統計的言語モデルの性能評価としてよく用いられる
クロスエントロピー）を計測した結果である。図３のグ
ラフから、ＰＰＭ＋＋の場合は文脈次数が高くなっても
クロスエントロピーが低いままで、ＰＰＭ、ＰＰＭ＊に
比べて高性能を維持していることが明らかである。
したＰＰＭ＊を、ここではＰＰＭ＋＋と呼ぶことにす
る。図３のグラフは、ＰＰＭ、ＰＰＭ＊、ＰＰＭ＋＋の
各々について、文脈次数に対する性能の高低（ここで
は、統計的言語モデルの性能評価としてよく用いられる
クロスエントロピー）を計測した結果である。図３のグ
ラフから、ＰＰＭ＋＋の場合は文脈次数が高くなっても
クロスエントロピーが低いままで、ＰＰＭ、ＰＰＭ＊に
比べて高性能を維持していることが明らかである。
【００４１】
【発明の効果】請求項１に記載の発明は、索引部はバッ
ファ部に記憶された記号列の位置番号列を記憶するもの
であるので、記憶量が従来より少なくてすむ。
ファ部に記憶された記号列の位置番号列を記憶するもの
であるので、記憶量が従来より少なくてすむ。
【００４２】請求項２に記載の発明は、請求項１に記載
の記号列処理装置において、ある記号の推定を行うため
に文脈を選択するのに際し、当該記号の直前の記号の推
定で選択した文脈の情報を利用することにより、従来よ
り次記号の推定性能を高めることができる。
の記号列処理装置において、ある記号の推定を行うため
に文脈を選択するのに際し、当該記号の直前の記号の推
定で選択した文脈の情報を利用することにより、従来よ
り次記号の推定性能を高めることができる。
【００４３】請求項３に記載の発明は、請求項１に記載
の記号列処理装置において、入力部で入力された記号列
が日本語文字であるときは、日本語文字の字種情報を用
いて次入力記号の推定のための文脈を選択することによ
り、従来より次記号の推定性能を高めることができる。
の記号列処理装置において、入力部で入力された記号列
が日本語文字であるときは、日本語文字の字種情報を用
いて次入力記号の推定のための文脈を選択することによ
り、従来より次記号の推定性能を高めることができる。
【図１】テキスト配列の例（ａ）と、そのsuffix array
の例（ｂ）である。
の例（ｂ）である。
【図２】この発明の一実施の形態である記号列処理装置
の機能ブロック図である。
の機能ブロック図である。
【図３】ＰＰＭ、ＰＰＭ＊、ＰＰＭ＋＋の各々につい
て、文脈次数に対する性能の高低を計測した結果を示す
グラフである。
て、文脈次数に対する性能の高低を計測した結果を示す
グラフである。
１ 記号列処理装置 ２ 入力部 ３ バッファ部 ４ 索引部 ５ 検索部 ６ 推定部
Claims (3)
- 【請求項１】 記号列を入力する入力部と、 記号列を記憶するバッファ部と、 この記憶された記号列の位置番号列を記憶する索引部
と、 前記入力部で入力された記号列の部分記号列について前
記バッファ部に記憶されている記号列中での出現位置を
前記索引部を用いて検索する検索部と、 この検索結果を用いて前記入力部への次入力記号を前記
索引部に記憶されている位置番号列の範囲内で推定する
推定部と、を備えている記号列処理装置。 - 【請求項２】 前記推定部は、前記次入力記号の前記推
定を行うために文脈を選択するのに際し、当該記号の直
前の記号の前記推定で選択した文脈の情報を利用するも
のである請求項１に記載の記号列処理装置。 - 【請求項３】 前記推定部は、前記入力部で入力された
記号列が日本語文字であるときは、日本語文字の字種情
報を用いて前記推定のための文脈を選択するものである
請求項１に記載の記号列処理装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11066251A JP2000259638A (ja) | 1999-03-12 | 1999-03-12 | 記号列処理装置 |
| US09/523,644 US6526401B1 (en) | 1999-03-12 | 2000-03-10 | Device for processing strings |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11066251A JP2000259638A (ja) | 1999-03-12 | 1999-03-12 | 記号列処理装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2000259638A true JP2000259638A (ja) | 2000-09-22 |
Family
ID=13310470
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11066251A Pending JP2000259638A (ja) | 1999-03-12 | 1999-03-12 | 記号列処理装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6526401B1 (ja) |
| JP (1) | JP2000259638A (ja) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| AU2001255219A1 (en) | 2000-04-04 | 2001-10-23 | Globalscape, Inc. | Method and system for conducting a full text search on a client system by a server system |
| JP3672242B2 (ja) * | 2001-01-11 | 2005-07-20 | インターナショナル・ビジネス・マシーンズ・コーポレーション | パターン検索方法、パターン検索装置、コンピュータプログラム及び記憶媒体 |
| US7113112B2 (en) * | 2001-04-16 | 2006-09-26 | Vindigo, Inc. | PPM-based data compression |
| US7259751B2 (en) * | 2003-02-03 | 2007-08-21 | The Board Of Trustees Of The Leland Stanford Junior University | Input systems and methods for the evaluation and optimization of same |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5875108A (en) * | 1991-12-23 | 1999-02-23 | Hoffberg; Steven M. | Ergonomic man-machine interface incorporating adaptive pattern recognition based control system |
-
1999
- 1999-03-12 JP JP11066251A patent/JP2000259638A/ja active Pending
-
2000
- 2000-03-10 US US09/523,644 patent/US6526401B1/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US6526401B1 (en) | 2003-02-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11416679B2 (en) | System and method for inputting text into electronic devices | |
| US10402493B2 (en) | System and method for inputting text into electronic devices | |
| US9460066B2 (en) | Systems and methods for character correction in communication devices | |
| CN102893239B (zh) | 电子设备的文本输入系统及文本输入方法 | |
| JP3998668B2 (ja) | 形態素解析装置、方法及びプログラム | |
| CN107704102B (zh) | 一种文本输入方法及装置 | |
| JP2683870B2 (ja) | 文字列検索システム及び方法 | |
| US5754847A (en) | Word/number and number/word mapping | |
| US8095526B2 (en) | Efficient retrieval of variable-length character string data | |
| US20180260381A1 (en) | Prepositional phrase attachment over word embedding products | |
| CN108475264B (zh) | 机器翻译方法和装置 | |
| US20160232455A1 (en) | Apparatus, system and method for an adaptive or static machine-learning classifier using prediction by partial matching (ppm) language modeling | |
| US5560037A (en) | Compact hyphenation point data | |
| KR20090007343A (ko) | 키패드의 멀티캐릭터 키를 사용한 문자 숫자식 데이터 입력장치와 방법 | |
| US5553283A (en) | Stored mapping data with information for skipping branches while keeping count of suffix endings | |
| CN114238564B (zh) | 一种信息检索方法、装置、电子设备及存储介质 | |
| Mani et al. | Real-time optimized n-gram for mobile devices | |
| CN101371252B (zh) | 字符处理装置、方法、程序以及存储介质 | |
| US6526401B1 (en) | Device for processing strings | |
| CN116975202B (zh) | 文档检索方法、装置、设备及存储介质 | |
| JP7775896B2 (ja) | 情報処理装置、情報処理方法、製造方法及びプログラム | |
| JP4015661B2 (ja) | 固有表現抽出装置、方法、プログラム及びそれを記録した記録媒体 | |
| JP2008059392A (ja) | 辞書検索装置および辞書検索処理プログラム | |
| Chia et al. | Morphologically-aware vocabulary reduction of word embeddings | |
| JPS63278174A (ja) | 翻訳装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| RD01 | Notification of change of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7421 Effective date: 20050609 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20060912 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20070306 |