TOP > 国内特許検索 > 共通パターン発見装置とプログラム、記憶媒体、及び共通パターン発見方法

共通パターン発見装置とプログラム、記憶媒体、及び共通パターン発見方法

国内特許コード P10A015647
整理番号 QP03019
掲載日 2010年8月31日
出願番号 特願2003-315129
公開番号 特開2005-084859
登録番号 特許第4385119号
出願日 平成15年9月8日(2003.9.8)
公開日 平成17年3月31日(2005.3.31)
登録日 平成21年10月9日(2009.10.9)
発明者
  • 池田 大輔
  • 山田 泰寛
  • 廣川 佐千男
出願人
  • 国立大学法人九州大学
発明の名称 共通パターン発見装置とプログラム、記憶媒体、及び共通パターン発見方法
発明の概要

【課題】本発明の解決しようとする問題点は、複数の情報間で共通のパターンを容易に発見することである。
【解決手段】本発明は、各テキスト情報から部分文字列を抽出する部分文字列取り出し手段11と、抽出した部分文字列の出現回数をカウントして同一の部分文字列ごとに出現回数の和をとって頻度とする頻度カウント手段12と、同一頻度ごとに部分文字列取り出し手段11が取り出した異なる部分文字列の数をカウントする部分文字列種類数カウント手段13と、頻度と異なる部分文字列の数との積を計算する総数計算手段14と、総数計算手段14によって計算された積と頻度との関係から、ピンポイントで出現するピークに位置の頻度を探すピーク発見手段15と、ピークが存在するとき該ピークの位置で頻度がカウントされた部分文字列を含むテキスト情報を抽出する情報抽出手段16とを備えたことを主要な特徴とする。
【選択図】図7

従来技術、競合技術の概要


ウェブ上には、HTMLやXML等で記述された多種多様のウェブページや、メール,ニュース等のアーカイブなど、マークアップ言語で記述されたテキストデータが大量に存在している。そしてこれらのテキストデータには同種の表現を繰返して記述するものが多数存在する。例えば、オークションのリストは1つのウェブページ中に商品に関するデータ(製品名、型番、購入日、傷の有無、保証書の有無など)が繰り返し表示される。また、新聞や株式に関するウェブサイト等では、分野や発刊日時、企業名等によって整理された記事や経済情報が整然とそれぞれ同一形式で表示されている。こうした共通のパターンを有する情報を発見するのは人間の判断以外には困難というのが現状である。唯一、ウェブページに関しては、共通のキーワードによって検索エンジンで探し、ブラウザで閲覧して要不要の判断を行い、抽出している。なお、多くのキーワードは、通常、自然言語から選ばれる。



このウェブページに関して、本発明者らは、ウェブ上の同種ファイルを集めることができればデータベースのような使い方が可能になるとの考えから、構造の類似するウェブページを簡単に収集することができる類似構造ファイル収集方法を提案した(特願2003-101944)。この際、自然言語の単語もしくは経験に基づく固定的な適宜の文字数で文字列を抽出するのでは、辞書の大きさや偶然に影響されるため、自然言語や偶然によらずに抽出する方法を採用した(非特許文献1参照)。



すなわち、この類似構造ファイル収集方法は、複数のウェブページ情報を対象とし、マークアップ言語で記述されたそれぞれのテキストデータから所定の計算法で決定された文字数の文字列を抽出し、その出現頻度をカウントするとともに、カウントされたすべての出現頻度の中から高頻出文字列として評価するため所定の計算法で決定された所定の割合以上の出現頻度で出現する文字列の文字数をカウントし、各ウェブページ情報でカウントされた文字数を比較して同一クラスタに構成できるウェブページ情報同士を統合することによって、対象の全ウェブページ情報を複数のウェブページ情報群に分け、母数が少ないウェブページ情報群をノイズクラスタとして除去し、複数のウェブページ情報の中から類似構造のウェブページ情報を抽出する。なお、上記計算法はウェブページ情報の頻出部分と非頻出部分との境界の数が初期値の近くで極小となるときの文字数と割合を、抽出する文字数と高頻出文字列の割合に決定するものである。そして、この類似構造ファイル収集方法は遺伝子の塩基配列情報の解析にも利用できるものであった。



しかし、本発明者らが提案したこの類似構造ファイル収集方法は、自然言語や偶然によらない画期的なものであったが、極小値の計算方法に課題が残るものであった。また、頻度を用いないものより計算時間は短くなったが、改善の余地があった。さらに、この方法は高頻度で出現するのは構造を示す記述部分と考えるため、タグ等が記述されたHTML等に適しており、文章表現などのあらゆる部分で共通のパターンを発見するものではなかった。



ところで、従来テキスト情報中の文章表現に関して、使用されている単語と出現頻度との間に、ジップの法則(Zipf’s law)が成立することはよく知られている。これはこの法則の発見者が、英文テキストと単語を材料にして発見した関係であるが、現在では欧州系等の言語、ウェブページの被リンク数、都市の人口の偏在状態、論文の参照件数などの出現頻度が絡む多くのまとまりのあるデータでごく普通に拡張的に成立すると考えられている法則である。



さて、このジップの第1法則は、テキスト中の単語を出現頻度順に並べたとき、順位rとその頻度fの積が定数Cになるというもので、f×r=Cの関係が成立するというものである。また、ジップの第2法則は、テキスト中の単語の頻度分布、とくに低頻度部分において、頻度がfである単語の種類数V(f)は頻度fとの間に、logV(f)=-a(logf)+bという関係が成立する、というものである。ここでa,bは情報ごとに存在する定数であり、a>0である。図13はジップの第2法則を示す説明図である。



しかしながら、このジップの法則は情報間で共通のパターンを有する情報を発見するのに寄与するものではない。さらに、ジップの法則は、本来、英文のように各単語がスペースを挟んで分離して配置されるような場合に成り立つ法則であるため、様々の助詞等を使って単語が次々と切れ目なく続く日本語や中国語等の言語、構造に関する記述を含むマークアップ言語、4つの塩基が様々のパターンで繰り返し並ぶDNA、さらには画像データ等の場合に、どのように文字列を抽出するかについては示唆するところがない。




【非特許文献1】池田,山田,廣川「Eliminating Useless Parts in Semi-structured Documents using AlternationCounts」,In Proceedings of the4th International Conference on Discovery Science,Lecture Notes in Artificial Intelligence(ドイツ国),Springer-Verlag,2001年11月,第2226巻,p.113-127

産業上の利用分野


本発明は、テキスト情報の中で共通する配列の文字列情報を簡単に収集することができる共通パターン発見装置とそのために使用するプログラム、記憶媒体、及び共通パターン発見方法に関する。

特許請求の範囲 【請求項1】
電子化された複数又は単数のテキスト情報を対象としてこのテキスト情報の中から最大長さまでのすべての長さの部分文字列を抽出する部分文字列取り出し手段と、前記部分文字列取り出し手段が抽出した部分文字列の出現回数をカウントして同一の部分文字列ごとに出現回数の和をとって頻度とする頻度カウント手段と、同一頻度ごとに前記部分文字列取り出し手段が取り出した異なる部分文字列の数をカウントする部分文字列種類数カウント手段と、前記頻度カウント手段がカウントした頻度と前記部分文字列種類数カウント手段がカウントした異なる部分文字列の数との積を計算する総数計算手段と、前記総数計算手段によって計算された積と前記頻度との関係から、変化率が閾値以上のピークが出現する位置の頻度を探すピーク発見手段と、ピークが存在するとき該ピークの位置の頻度と同一頻度の部分文字列を含むテキスト情報を抽出する情報抽出手段とを備え、
前記テキスト情報に同一の部分文字列が存在する場合に、この部分文字列の頻度の大きさに比例して前記積の値の大きさを増し、頻度に関してピークを形成する分布にして、このピークの位置の頻度を有する部分文字列を基に前記複数又は単数のテキスト情報間で共通する配列をもつ文字列情報を発見することを特徴とする共通パターン発見装置。

【請求項2】
コンピュータを、電子化された複数又は単数のテキスト情報を対象としてこのテキスト情報の中から最大長さまでのすべての長さの部分文字列を抽出する部分文字列取り出し手段、前記部分文字列取り出し手段が抽出した部分文字列の出現回数をカウントして同一の部分文字列ごとに出現回数の和をとって頻度とする頻度カウント手段、同一頻度ごとに前記部分文字列取り出し手段が取り出した異なる部分文字列の数をカウントする部分文字列種類数カウント手段、前記頻度カウント手段がカウントした頻度と前記部分文字列種類数カウント手段がカウントした異なる部分文字列の数との積を計算する総数計算手段、前記総数計算手段によって計算された積と前記頻度との関係から、変化率が閾値以上のピークが出現する位置の頻度を探すピーク発見手段、ピークが存在するとき該ピークの位置の頻度と同一頻度の部分文字列を含むテキスト情報を抽出する情報抽出手段として機能させるためのプログラムであって、
前記テキスト情報に同一の部分文字列が存在する場合に、この部分文字列の頻度の大きさに比例して前記積の値の大きさを増し、頻度に関してピークを形成する分布にして、前記情報抽出手段によって抽出された該ピークの位置の頻度を有する部分文字列を基に前記複数又は単数のテキスト情報間で共通する配列をもつ文字列情報を発見することを特徴とするプログラム。

【請求項3】
請求項記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。

【請求項4】
電子化された複数又は単数のテキスト情報を対象としてこのテキスト情報の中から部分文字列取り出し手段によって最大長さまでのすべての長さの部分文字列を抽出し、頻度カウント手段によって同一の部分文字列ごとに出現回数の和をとって頻度とするとともに該頻度を有する異なる部分文字列の数を部分文字列種類数カウント手段によってカウントし、総数計算手段によって前記頻度と前記異なる部分文字列の数との積を計算し、更にピーク発見手段によって前記積と前記頻度との関係から変化率が閾値以上のピークが出現する位置の頻度を探し、ピークが存在するとき情報抽出手段によって該ピークの位置の頻度と同一頻度の部分文字列を含むテキスト情報を抽出する共通パターン発見方法であって
前記テキスト情報に同一の部分文字列が存在する場合に、この部分文字列の頻度の大きさに比例して前記積の値の大きさを増し、頻度に関してピークを形成する分布にして、前記情報抽出手段によって抽出された該ピークの位置の頻度を有する部分文字列を基に前記複数又は単数のテキスト情報間で共通する配列をもつ文字列情報を発見することを特徴とする共通パターン発見方法。
産業区分
  • 計算機応用
  • 微生物工業
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2003315129thum.jpg
出願権利状態 権利存続中
上記の特許・技術に関心のある方は、下記問合せ先にご相談下さい。


PAGE TOP

close
close
close
close
close
close
close