Top > Search of Japanese Patents > COMMON PATTERN DETECTING DEVICE AND PROGRAM, STORAGE MEDIUM, AND COMMON PATTERN DETECTING METHOD

COMMON PATTERN DETECTING DEVICE AND PROGRAM, STORAGE MEDIUM, AND COMMON PATTERN DETECTING METHOD

Patent code P10A015647
File No. QP03019
Posted date Aug 31, 2010
Application number P2003-315129
Publication number P2005-084859A
Patent number P4385119
Date of filing Sep 8, 2003
Date of publication of application Mar 31, 2005
Date of registration Oct 9, 2009
Inventor
  • (In Japanese)池田 大輔
  • (In Japanese)山田 泰寛
  • (In Japanese)廣川 佐千男
Applicant
  • (In Japanese)国立大学法人九州大学
Title COMMON PATTERN DETECTING DEVICE AND PROGRAM, STORAGE MEDIUM, AND COMMON PATTERN DETECTING METHOD
Abstract PROBLEM TO BE SOLVED: To easily detect common patterns among a plurality of information.
SOLUTION: This device comprises a part character string taking-out means 11 for extracting a part character string from the respective text information, a frequency-counting means 12 for counting the occurrence frequency of the extracted part character string and for summing up the occurrence frequency for each identical part character string to provide the frequency, a part character string kind number counting means 13 for counting the number of different part character strings taken out by the part character string taking-out means 11 for every same frequency, a total number calculating means 14 for calculating the product of the frequency by the number of different part character strings, a peak detecting means 15 for detecting the frequency of peak positions, occurring as a pinpoint from the relation between the product calculated by the total number calculating means 14 and the frequency, and an information extracting means 16 for extracting the text information, including the part character string of which frequency is counted at the peak position, when the peak exists.
Outline of related art and contending technology (In Japanese)

ウェブ上には、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

Field of industrial application (In Japanese)

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

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

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

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

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

※Click image to enlarge.

JP2003315129thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close