JP2009099030A

JP2009099030A - 処理内容判定装置および処理内容判定方法

Info

Publication number: JP2009099030A
Application number: JP2007271325A
Authority: JP
Inventors: Akihiro Sakano; 晃弘坂野
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2007-10-18
Filing date: 2007-10-18
Publication date: 2009-05-07

Abstract

【課題】所定の関連法則を用いて記述された処理内容について同一性あるいは類似のより的確な判定が可能な処理内容判定装置および処理内容判定方法を得ること。
【解決手段】類否の判定を行う第１および第２の比較対象記述データ１０３、１０４は記述ルール解析部１１２でこれらに共通の関連法則を用いてたとえば木構造に解析され、比較程度設定部１０７で一例として枝刈りが行われたブロックを対象として類似度演算部１１４が比較対象両者の類似度を演算する。演算結果１１５は類否あるいは類似の程度として出力され、類似判定表示部１０８で表示される。
【選択図】図１

Description

本発明は、文法という関連法則を用いて文章同士の比較を行う場合のように、所定の関連法則を用いて組み立てられた処理内容の同一性の有無の判定あるいは類似の度合いの検出を行う処理内容判定装置および処理内容判定方法に関する。

ある言語で記述された著作物Ａと、他の言語で記述された著作物Ｂとが存在するものとする。本明細書で著作物とは、創作されたソースやドキュメントをいう。たとえば盗作であるかどうかを判断する際には、判断の対象となる２つの著作物Ａ、Ｂの類似点の有無あるいは類似度が問題となる。そこで、本発明に関連する技術として、著作物Ａ、Ｂの類似点を検出する関連技術が各種提案されている（たとえば特許文献１、特許文献２参照）。

このうち、特許文献１では、所定のプログラム言語で記述されたソースコードから類似のソースコード片を抽出する技術を開示している。本願発明に関連するこの第１の関連技術では、ソースコード群に含まれるソースコードを総当りで比較して類似のソースコード片を抽出する従来の手法が、ソースコード群に含まれるソースコードの数が大量に存在する場合に膨大な処理時間を要するという問題を解消している。すなわち、この第１の関連技術では、指定されたソースコード片を基準として類似するソースコード片を抽出するようにして、すべてのソースコードを総当りで類似比較して類似するソースコード片を抽出する従来の手法と比較して処理結果を短時間で得られるようにしている。

次に、特許文献２に記載された第２の関連技術について説明する。第２の関連技術は、ソースプログラムを変更した場合に、どの程度の変更が加えられたかを確認するための技術である。

図４は、この第２の関連技術によるソースプログラム比較情報生成システムの構成の概要を表わしたものである。このソースプログラム比較情報生成システム４００では、ソースプログラム読み込み部４０１が変更前ソースプログラム４０２と変更後ソースプログラム４０３の読み込みを行う。基本比較情報解析部４０４は、これらのソースプログラム４０２、４０３の行単位での一致・不一致を比較して変更行及び比較行を抽出する。そして、変更行または比較行から構成される変更部分を示す変更ブロックとその他の未変更ブロックとに分類する。この基本比較情報解析部４０４では、ソースプログラムを各行ごとに対比して、１または連続した複数行からなる変更が行われていない未変更ブロックと、変更が行われた変更ブロックに分ける。

詳細比較情報解析部４０５は、未変更ブロックの間にそれぞれ挟まれた領域として存在する変更ブロック内の比較行と変更行との組合せに対して詳細な比較情報を作成する。具体的には行類似度演算部４１１が、変更前ソースプログラム４０２と変更後ソースプログラム４０３の双方について変更ブロック内の各行の類似度を、行のすべての組み合わせに対して算出する。

次に、ブロック類似度演算部４１３は行類似度演算部４１１で算出された各組合せごとの行の類似度に基づき、変更ブロックにおける組合せパターンのすべてについて、変更ブロック全体としての類似度の算出を行う。

最後に設けられた変更種別判定部４１４は、以上の処理の結果、ブロック類似度が最大となった組合せパターンに基づき、変更ブロックの各行について、変更種別の判定を行う。具体的には組合せパターンで、比較行と変更行とが対応付けされている場合はその行について「修正」があったものとする。また、対応付けのされていない比較行についてはその行が「削除」されたものとし、対応付けのされていない変更行があった場合には、その行が「追加」されたものと判定するようにしている。

次に、特許文献以外の本発明に関連する技術について概要を説明する。ＣＦＧ（Context Free Grammar：文脈自由文法）やＢＮＦ（Backus Naur Form）に関する解説が本発明の第３の関連技術として行われており（たとえば非特許文献１参照）、ＡＮＳＩＣ（American National Standard for Information Systems - Programming language C）（８９）やその他の言語のＢＮＦ実装例が本発明の第３の関連技術として行われている（たとえば非特許文献２および非特許文献３参照）。また、Ｐｒｏｌｏｇ（PROgramming in LOGic：論理プログラミング）によるＤＣＧ（Definite Clause Grammar：確定節文法）の解説が、第３の関連技術における非特許文献３に記載されている。ただし、「ＪＩＳＸ３０１２：２００１Ｐｒｏｌｏｇ」は、基本部分のみでＤＣＧは含まれていない。このような従来の本発明に関連する技術では、ソースの文字列差分を抽出するようになっている。

以上、本発明の関連技術を各種示したが、著作物Ａ、Ｂの類似点を検出するこれらの技術には、一般に次のような傾向がある。
（ａ）ソースコードやドキュメントをそれらの構造ではなく文字列として直接比較する。
（ｂ）文字列の比較を行うときに単一の言語で比較を行い、異なった言語間での比較は行わない。
（ｃ）比較単位としてのブロックの設定がない。

たとえば、図４に示した本発明の第２の関連技術では、変更後ソースプログラム側の変更行または変更部分に対応する変更前ソースプログラム側の比較行から構成される変更部分を変更ブロックとし、未変更部分を未変更ブロックとする形でブロック（領域）の区分けを行っている。すなわち、第２の関連技術で「ブロック」とは変更箇所と未変更箇所を区分けするためのものでしかなく、しかもこれらの類似度は、主として行単位にこれらのソースプログラムの差分をとって統計的な手法で測定している。

特開２００６−０１８６９３号公報（第００２２段落、図３）特開２００３−２８０９０３号公報（第００１０、第００１１段落、図１、図３）五月女健治著「bison／flexプログラムジェネレータon MS-DOS」啓学出版、１９９４年１月２５日、ｐｐ．２８１−３１８ http://www.quut.com/c/ANSI-C-grammar-y.html http://www.csci.csusb.edu/dick/samples/index.html http://bach.istc.kobe-u.ac.jp/prolog/intro/lang.html

以上説明したようにソースやドキュメント等の著作物の類似性を判定しようとするとき、本発明の関連技術では、比較の対象となる著作物Ａ、Ｂが共通の言語からなっており、これらの比較は単純に差分をとることによって行っていた。このため、次のような問題が指摘されていた。

（ａ）開発ツールとしてのソースの自由度に影響されない差異確認を行うことができなかった。すなわち、オブジェクトに差異がない程度のソースの違いを無視して、大きな相違点を判断することが困難とされた。
（ｂ）したがって、たとえば特許権や著作権の侵害の有無の判断を行おうとするときに、それぞれの類似ソースを検出してこれを元のソースと単純に置き換えただけのようなものであると判断するには構造の同一性を判断することが重要であるが、このような構造の同一性の判断が困難とされた。
（ｃ）この結果として、特許権や著作権の侵害に当たる類似のドキュメントの検出が不得意とされた。

たとえば第２の関連技術では、主として行単位にこソースプログラムの差分をとるようにしている。したがって、これを一般的な著作物の類似を判別する技術に適用したとすると、特定された著作物に対して不正な改ざんを行った場合のその箇所を探したり、著作物Ａ、Ｂの２点間における著作物の変更点を探したりするといった用途に対しては有用な技術となる。しかしながら、著作物Ａ、Ｂの構造の違いを認識したりその違いを視覚化したりするといった用途や、ソフトウェアを異言語や別プラットフォームに移植した結果の同一性を言語非依存で確認したい、あるいは、文字列や言語を置き換えただけのような不正な流用を確認したいといったニーズには、応えることができないという問題があった。

以上、著作物の同一性や類似度の判定あるいは判断について説明したが、所定の関連法則を用いて記述された処理内容一般の類否判定や類否判断を行うとき、同様の問題があった。

そこで本発明の目的は、所定の関連法則を用いて記述された処理内容について同一性あるいは類似のより的確な判定が可能な処理内容判定装置および処理内容判定方法を提供することにある。

本発明では、（イ）所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述を入力する比較対象記述入力手段と、（ロ）これら比較対象となる記述を、前記した関連法則を用いてそれぞれ解析し、それぞれの記述内容を構成する記述構成内容同士の関連を表わした記述構成内容関連マップを生成する記述構成内容関連マップ生成手段と、（ハ）この記述構成内容関連マップ生成手段で生成された記述構成内容関連マップを前記した比較対象となる記述同士で比較して、これらマップの一致の程度を類似度として演算する類似度演算手段とを処理内容判定装置に具備させる。

また、本発明では、（イ）所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述を入力する比較対象記述入力ステップと、（ロ）これら比較対象となる記述を、前記した関連法則を用いてそれぞれ解析し、それぞれの記述内容を構成する記述構成内容同士の関連を表わした記述構成内容関連マップを生成する記述構成内容関連マップ生成ステップと、（ハ）この記述構成内容関連マップ生成ステップで生成された記述構成内容関連マップを前記した比較対象となる記述同士で比較して、これらマップの一致の程度を類似度として演算する類似度演算ステップとを処理内容判定方法に具備させる。

このように本発明では、所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述を入力し、これらを比較する前に前記した所定の関連法則を用いてそれぞれの記述内容を構成する記述構成内容同士の関連を表わした記述構成内容関連マップを生成する。記述構成内容関連マップは、たとえば階層関係を示すマップとしての構文解析木あるいはネットワークで関係を相互に表わしたマップとしてのネットワーク型データ構造となる。類似度の演算は、記述構成内容関連マップを対比することで行う。これにより、たとえば親子関係の親同士や子供同士の同一性や差分を求めながら類似度（類否あるいは似通った度合い）を演算することができ、先行技術よりも的確な判定が可能になる。

図１は本発明の実施の形態における処理内容判定装置を使用した処理内容判定システムの構成を表わしたものである。この処理内容判定システム１００は、第１の比較対象記述データ格納部１０１および第２の比較対象記述データ格納部１０２を備えている。第１の比較対象記述データ格納部１０１には、第１の比較対象記述データ１０３が格納されており、第２の比較対象記述データ格納部１０２にはこの第１の比較対象記述データ１０３と比較する第２の比較対象記述データ１０４が格納されている。第１および第２の比較対象記述データ１０３、１０４は、たとえば小説やプログラム等の著作物が代表的である。

処理内容判定装置１０５は、これら第１および第２の比較対象記述データ１０３、１０４を入力する比較対象記述データ入力部１１１と、比較対象記述データ入力部１１１から入力されたこれら比較対象記述データ１０３、１０４に記述されている関連法則（以下、記述ルールという。）を解析する記述ルール解析部１１２と、解析した記述ルール１１３を入力してこれら第１および第２の比較対象記述データ１０３、１０４の類似度を演算する類似度演算部１１４を備えている。比較対象記述データ１０３、１０４は、共に記述ルールで構成されたブロックの集合と考えることができる。ここで記述ルール解析部１１２は、外部の記述ルールデータベース１０６を参照して記述ルールの解析を行う。

すなわち記述ルール解析部１１２は、第１および第２の比較対象記述データ１０３、１０４に共通した記述ルールを解析する部分である。たとえばこれが小説、特許明細書あるいはソースプログラムのような関連法則（ここでは言語）によって記述されているものであれば、この言語が異なる場合にこれを統一する前処理が必要である。一例をあげると、第１の比較対象記述データ１０３が英語によって記述されており、第２の比較対象記述データ１０４が日本語によって記述されていれば、これらを共通言語（英語、日本語あるいはエスペラント語のような両言語の共通言語）に翻訳する前処理を行う必要がある。記述ルールデータベース１０６には、このような前処理部分を実行する際のデータベース部分が含まれてよい。

記述内容が異なれば前処理の手法も異なる。たとえば記述内容が言語ではなくゲームの内容である場合で、サラリーマンの出世ゲームと政治家の出世ゲームの著作権の類否を論じる場合、登場人物の役割等の各種要素を考慮しながら比較対象となる一方のゲームの世界あるいは共通したゲームの世界に両者を配置し直す前処理を的確に行うことで、類否判定の確度が増す。

記述ルール解析部１１２は、このように共通言語に翻訳されたもの、あるいは元々共通言語で記述されたものの内容を解析する。したがって第１の比較対象記述データ格納部１０１および第２の比較対象記述データ格納部１０２には、それぞれが内容を解析できる関連法則を用いで作成された比較対象記述データ１０３、１０４が格納されている必要がある。たとえば、日本語等の言語は、文法という関連法則があり、これによって内容を解析することができる。言語に限らず、前記したゲームのように各部の連結関係を解析できる関連法則が規定されている記述は第１および第２の比較対象記述データ１０３、１０４として本発明を適用することができることは当然である。

ここで記述ルール解析部１１２の解析とは、たとえば第１の比較対象記述データ１０３内で、どのように各内容が関連しているかを、記述構成内容関連マップを使用して調べることをいう。たとえば、親、子、孫といったような階層関係や、同一の部署の人物、同一の趣味のクラブに属している人物、同一の年齢というようなネットワークで接続されるような関係を調べることである。

類似度演算部１１４は、第１および第２の比較対象記述データ１０３、１０４についてそれぞれ解析したこのような記述ルール１１３の対応する箇所あるいは対応するグループについて比較を行い、対応するものの同一性の有無や差分の量を測定して、両記述内容が似ているかの度合いをアナログ的な結果として演算したり、類否という２値の結果を演算したりする。このとき、比較程度設定部１０７で比較の程度（深さあるいは範囲）を設定するようにしてもよい。たとえば、階層型の解析結果を有する記述データの類否を比較するものであれば、基本となる階層から数えて所定の階層までを類否の演算の対象としてもよい。次に説明する実施例では、これを「枝刈り」という概念で実現している。

類似度演算部１１４の演算結果１１５は類似判定表示部１０８に出力される。類似判定表示部１０８はプリンタのような記録媒体に出力するものであってもよいし、液晶ディスプレイのような表示内容を出力するものであってもよい。また、処理内容判定装置１０５と類似判定表示部１０８は通信ケーブルで接続されていてもよいし、通信ネットワークを介して接続されていてもよい。また、これらの間に演算結果１１５を一時的にあるいは半永久的に保存するハードディスク等の記憶デバイスが介在してもよい。

類似判定表示部１０８に出力される演算結果は、前記したように類似の程度を表わすものであってもよいし、類否を判定したものであってもよい。処理内容判定装置１０５がどのような用途に使用されるかによって出力形態が異なることになる。比較程度設定部１０７がこのような出力形態の設定を行うことも自由である。

以上説明したような本実施の形態の処理内容判定装置１０５によれば、記述形式が異なった比較対象の記述データ同士であっても、翻訳のような前処理を行うことで、類似判断を行うことができ、比較対象の制限が緩和される。また、記述ルールを基に類似判断を行うので、文法に限らず、たとえば所定の関連法則を用いて組み立てられた気象に関する記述を用いて２つの台風の類似判断を行う場合のように、自然現象の比較のような広範囲の類似判断が可能になる。

更に、関連法則に基づいて類似の判断を行うので、客観的な判断が可能である。また、比較程度の設定を行うようにすれば、処理内容判定装置１０５の処理目的に応じて効率的な処理を行うことができる。

なお、図１に示した処理内容判定装置１０５は、図示しないＣＰＵ（Central Processing Unit）あるいはプロセッサと、同じく図示しない類似判定用の制御プログラムを格納したハードディスク等の記憶媒体を用いたコンピュータとして実現することができる。この場合、第１の比較対象記述データ格納部１０１、第２の比較対象記述データ格納部１０２および記述ルールデータベース１０６は、ハードディスクや通信ネットワーク上に配置したサーバで構成することができ、比較程度設定部１０７は図示しないキーボードやポインティングデバイスで構成することができる。

図２は、本発明の一実施例による処理内容判定装置の構成の概要を表わしたものである。この処理内容判定装置２００は、メタ言語ソース２０１を読み込んで対応する構文解析器２０２を出力するメタ言語２０３を備えている。ここでメタ言語とは、既存の言語の文法解析機能を生成するツールである。代表的には、構文解析を行うＣプログラムを自動生成するツールとしての「Ｙａｃｃ（Yet Another Compiler Compiler）」や、「Ｐｒｏｌｏｇ」を挙げることができる。

この処理内容判定装置２００に入力される著作物としての第１のソース・言語２０４および第２のソース・言語２０５は、互いに異なる言語で記述されている。第１の構文解析器２０６は第１のソース・言語２０４を読み込んで、第１の構文解析木２０７を出力する。第２の構文解析器２０８は第２のソース・言語２０５を読み込んで、第２の構文解析木２０９を出力する。

構文解析木比較器２１１は、比較単位基準２１２と同様に類似度判定基準２１３を比較前に読み込むようになっている。次に構文解析木比較器２１１は、比較対象となる第１の構文解析木２０７および第２の構文解析木２０９を読み込む。そして、比較単位基準２１３で指定された条件に従い、第１および第２の構文解析木２０７、２０９を各々部分木の集合に分割する。次に構文解析木比較器２１１は、第１の構文解析木２０７の各部分木と第２の構文解析木２０９の各部分木の総当りの組み合わせで比較を行う。そして、すべての比較結果について、類似度判定基準２１３での指定に基づいて類似度を判定し、比較結果として比較結果リスト２１４を出力するようになっている。

このように本実施例の処理内容判定装置２００は、形式言語の構文解析器２０２を作る処理部分と、言語ごとの構文解析木２０７、２０９を生成する処理部分と、これらの構文解析木２０７、２０９を比較する処理部分を備えている。このうちの言語ごとの構文解析木２０７、２０９を生成する処理は、必要とされる場合のみ実施される。なお、処理内容判定装置２００は多くの構成を採り得るが、本実施例ではこのうちの特定のパターンのみを示すことにする。

ところで図２に示した処理内容判定装置２００で構文解析器２０２は、メタ言語２０３から生成される。生成された構文解析器２０２は、破線でそれぞれ示したように第１の構文解析器２０６および第２の構文解析器２０８として利用されるようになっている。このように異なる２種類の構文解析器２０６、２０８を作成し利用する代わりに、１種類の構文解析器が使用されるものであってもよい。

図３は、構文解析木比較器の構成を具体的に表わしたものである。これら図２と図３を使用して、本実施例の処理内容判定装置２００の説明を行う。なお、本実施例ではメタ言語２０３を扱っている。そこで、図面では、あえてデータとこれらの処理ステップの表記の区別を行わないようにしている。データとこれらの処理ステップの表記は部分的に可能であるが、処理対象がデータにもなるので同じものを部分ごとに表記を変えていると別なものに見えてしまうおそれがあるためである。

まず、最初の処理手順としてのステップＳ３０１では、前記したようにメタ言語２０３がメタ言語ソース２０１を読み込んで、対応する構文解析器２０２を出力する。メタ言語ソース２０１は、たとえば、比較したい著作物を記した言語の文法と、文法構造を木構造に変換する副作用からなっている。

著作物の言語としては、文法が、ＣＦＧ（Context Free Grammar:文脈自由文法）、ＤＣＧ（Definite Clause Grammar）等の情報処理が可能な理論に基づく形式言語と解釈できるものであれば自然言語であっても人工言語であっても構わない。ただし、実際には、その言語を処理できる「Ｙａｃｃ」（Yet Another Compiler-Compiler）あるいは「Ｐｒｏｌｏｇ」（PROgramming in LOGic:論理プログラミング）といったメタ言語２０３に位置付くものが必要になる。「Ｐｒｏｌｏｇ」は元来、自然言語解析のために開発されたものである。

また、実装上の工夫として、メタ言語ソース２０１は、プリプロセッサ（preprocessor）が必要な言語体系では予め処理を済ませておく。メタ言語２０３から出力された構文解析器２０２は、ステップＳ３０２で第１および第２の構文解析器２０６、２０８として使用されることになる。

次のステップＳ３０２で、メタ言語２０３とメタ言語ソース２０１から得られた第１および第２の構文解析器２０６、２０８は、各々の対象となる言語で記述された著作物を読み込む。ここでは、著作物としての第１のソース・言語２０４および第２のソース・言語２０５の読み込みが行われる。第１の構文解析器２０６は第１のソース・言語２０４を読み込んで、第１の構文解析木２０７を出力する。第２の構文解析器２０８は第２のソース・言語２０８を読み込んで、第２の構文解析木２０９を出力する。たとえば、第１の構文解析器２０６はＣ言語ソースから、その構文解析木を生成する機能を備えており、第２の構文解析器２０８はＢＡＳＩＣ言語ソースから、その構文解析木を生成する機能を備えていると考えるとよい。

このようにステップＳ３０２で第１および第２の構文解析木２０７、２０９として表現されたことで、言語の異なる２つの著作物は対等な記述形式となり、形式的な比較が可能になる。もちろん、これらの出力形式はツリー構造、ネットワーク構造、ＸＭＬ（Extensible Markup Language）等の各種のものが考えられるが、両者を比較するには表現形式をいずれか１つに統一しておく必要がある。たとえば、記述された命令を逐次的に実行し、処理の結果に応じて変数の内容を変化させていくプログラミング言語としての手続き型言語は、順接、条件分岐、繰り返し、跳躍で構成されている。これをＸＭＬで次の第１〜第５の関連法則Ｒ₁〜Ｒ₅によって置き換える。なお、たとえばネットワーク構造については変換形式自体を検討する必要があるが、これは本発明の趣旨から外れるため説明を割愛する。

関連法則Ｒ₁……「順接」は、各文に対応する同レベルのタグの並びとする。
関連法則Ｒ₂……「条件分岐」は、分岐条件式と分岐する同レベルのタグの並びとする。
関連法則Ｒ₃……「繰り返し」は、繰り返し条件式と繰り返す同レベルのタグの並びとする。
関連法則Ｒ₄……「跳躍」は、ラベルを示すトークンを変換したノードをポイントするタグとする。
関連法則Ｒ₅……「直接再起呼び出し」はタグとして特別扱いしない（タグオプション間で比較）。

ここで、関連法則Ｒ₅の「直接再帰呼び出し」とは、手続きの中から同じ手続きを呼び出すことであり、手続き（たとえばａ）から呼び出した手続き（たとえばｂ）から更に元の手続き（ａ）を呼び出すような間接再帰呼び出しとは区別している。また、トークンとは、空白やコメントを省いた認識の最小単位をいう。

Ｃ言語を例にとり、メタ言語の１つとしてのＢＮＦ（Backus Naur Form）に従って、第１および第２の構文解析木２０７、２０９をＸＭＬに変換する例を挙げる。ただし関連法則Ｒ₁の例については、ＢＮＦが複雑すぎることと、本質的に同等な文を同一の深さに並列列挙することが本実施の形態での関連法則であり、本質的ではないのでここでは例示しない。

関連法則Ｒ₂の例
[条件分岐のＢＮＦ]
selection_statement
: IF '(' expression ')' statement-block
| IF '(' expression ')' statement-block ELSE statement-block
| SWITCH '(' expression ')' statement-block
;
[条件分岐のＸＭＬ(IF '(' expression ')' statement-block ELSE statement-blockのみ例示)]
<select key=’if’ expression=’’>
<statement-block eval=’true’>…</statement-block>
<statement-block eval=’false’>…</statement-block>
</select>

関連法則Ｒ₃の例
[繰り返しのＢＮＦ]
iteration_statement
: WHILE '(' expression ')' statement-block
| DO statement WHILE '(' expression ')' ';'
| FOR '(' expression_statement expression_statement ')' statement-block
| FOR '(' expression_statement expression_statement expression ')' statement-block
| FOR '(' declaration expression_statement ')' statement-block
| FOR '(' declaration expression_statement expression ')' statement-block
;
[繰り返しのＸＭＬ(FOR '(' expression_statement expression_statement expression ')' statement-blockのみ例示)]
<iteration key=’for’ eval=' expression_statement’>
<statement-block>…</statement-block>
</iteration>

関連法則Ｒ₄の例
[跳躍のＢＮＦ]
jump_statement
: GOTO IDENTIFIER ';'
| CONTINUE ';'
| BREAK ';'
| RETURN ';'
| RETURN expression ';'
;
labeled_statement
: IDENTIFIER ':' statement-block
| CASE constant_expression ':' statement-block
| DEFAULT ':' statement-block
;
[跳躍のＸＭＬ(GOTO IDENTIFIER ';' およびIDENTIFIER ':' statement-blockのみ例示)]
<jump key=’goto’ eval=’ <IDENTIFIER>’/>
:
<label key=’ <IDENTIFIER>’/>

関連法則Ｒ₅の例
直接再起呼び出し自体は、Ｒ１〜Ｒ４のＢＮＦに自然に内包されており、独自のＢＮＦは提示しない。
[直接再起呼び出しのＸＭＬ]
<block rootid=’<FUNCTIONAL>’>
:
<statement procid=’<FUNCTIONAL>’>
:
<／block>

ここで「ＦＵＮＣＴＩＯＮＡＬ」はＣ言語の関数に対応し、これが一致するものを再帰とする。他の手続き型言語では、手続き名（たとえば「ＰＲＯＣＥＤＵＲＥ」）に置き換えて考えるとよい。

なお、関連法則Ｒ₁の例についての記載を省略したが、任意の文の変換イメージをここでは、「statement」タグという名前で表わしている。

以上説明した例で、タグは図３に示した木構造のノードを表わしている。オプションは、ソースとなる著作物の記述や特性を示すために用いる。ＸＭＬへの変換イメージは仮のものである。したがって、ＸＭＬタグにおける「statement-block」、「select」、「iteration」、「jump」、「label」のオプションは、予約語と対応した「key」や評価と対応させた「eval」等の言葉の概念を有するものである必要はない。ＸＭＬタグにおいてタグ名、オプション、タグ階層で、関連法則Ｒ₁〜関連法則Ｒ₅のような構造が決定できるようにするようにすればよい。

この例で「key」としているのは、ＢＮＦの式にマッチングした人工言語の予約語を意味する例である。大文字の文字列は、Ｃ言語の任意、または特定のトークン（予約語やユーザ定義語）を示している。また、例で、「eval」としているのは、ユーザ定義語や、式を表わしている。

形式言語の言語体系は、Ｃ言語のような構造化された手続き型言語以外のものもある。たとえば関数型言語や論理型言語の場合には、文自体が、木構造をしており、ソースの処理方式の類似性の判定にそのまま利用することが期待できる。この一方で、構造化されてない手続き型言語は、木構造で表現するのは難しい可能性がある。

自然言語の中にも、英語のように比較的、形式言語として取り扱いやすいものがある。このような自然言語は、ドキュメントの類似性判定への応用も考えられる。ただしそのような自然言語であっても散文詩のようなものは規制の文法体系を取っていないか、または変形生成文法で説明はできるものもあるが、句読点の喪失などで、構文解析木を生成する処理が難しいと考えられる。

なお、本実施例の処理内容判定装置２００は、構文解析についての厳密さを追及する必然性はない。すなわち、構文を概要レベルでも解析できるものであれば、言語非依存な構文解析木を生成し比較対象としての著作物の類否を判断することができる。このため、本発明の適用範囲は広い。本発明では、構文解析木の属性として、著作物のトークンやその種類を含むことが可能である。

次にステップＳ３０３について説明する。
構文解析木比較器２１１は、次の要領で、第１および第２の構文解析木２０７、２０９を比較する。

第１の構文解析木比較器２１１は、まず比較単位基準２１２と類似度判定基準２１３を比較前に読み込む。これら比較単位基準２１２と類似度判定基準２１３および第１および第２の構文解析木２０７、２０９の読み込み順序は任意でよい。

次に、構文解析木比較器２１１は、これら読み込んだ第１および第２の構文解析木２０７、２０９をより細かい単位ブロック（枝）に分割する。この分割は、ブロック分割ルール（枝刈りルール）に従う。このブロック分割ルールについて説明する。

ブロックに分割する比較単位基準２１２は、環境設定（設定ファイル、レジストリ、環境変数等）として実装される。比較単位基準２１２でブロック化する際のブロックの単位等の条件を設定し、構文解析木比較器２１１は、比較前にこの設定した条件を読み込む。

ブロック化する条件のうちの必須条件は、関数定義やメソッド定義のような根（ｒｏｏｔ）から分割する単位を指定するために利用する。先に示したＸＭＬへの変換例では、タグの階層の深さを指定し、構文解析木の読み込み時にその深さ以上をブロックとして枝刈りを行う。ブロック化する具体的な単位としては、手続きの部分ではないまとまり（たとえばＣ言語の関数）やメソッドレベルのスコープが想定される。

Ｃ＃のような言語では、関数スコープの上位に、クラスや名前空間のスコープがある。このため、根（ｒｏｏｔ）の直下に関数があるとは限らない。したがって、ブロック分割ルールは調整が必要になる。またブロック化する条件に対する任意の付随条件として、ブロック化した結果、あまりにも階層の低い枝（０階層や１階層）は、比較対象から除外することも可能とする。比較目的によって、要、不要の差異が出るが、たとえばアルゴリズムの一致を問うのであれば意味の無い比較であり、これを省略することで組み合わせの数が減少し、大幅に処理時間を短縮することができる。

この一方で、文書の著作権侵害を問うのであれば、階層のより低い枝のレベルによる比較も必要になる。前記した任意の付随条件は、トリビアルな部分木は比較しないという趣旨で設けられるものであり、比較対象となる部分木の末端まで見ないという意味ではない。

本実施例で使用される枝刈ルールはトップダウンに行われる。このため、全体の構文のような検知から比較単位の部分木を生成する。これによって、トリビアルな部分木も出現するものの、所望の処理単位を、確実に部分木として取り出すことができる。トリビアルな部分木は簡単に判定できるものも多い。そこで、トリビアルな部分木であると判定できた段階でこのトリビアルな部分木を切り捨ててしまうと処理効率がよい。

さて、第１および第２の構文解析木２０７、２０９をより細かい単位ブロック（枝）に分割すれば、これら第１および第２の構文解析木２０７、２０９はこれらの単位ブロック（枝）の集合であるとみなすことができる。特別な場合としてブロックを全体とみなしてもよい。比較は、第１および第２の構文解析木２０７、２０９のそれぞれのブロック（枝）の集合について、第１の構文解析木２０７の枝Ｘと第２の構文解析木２０９の枝Ｙの組み合わせで行われる。比較したい片側の１つの単位ブロック（枝）に対し、他方にクリエをかけるため、他方側の単位ブロック（枝）の数をｎとすると、比較のための検索にかかる時間計算量はＯ（ｎ）となる。ハッシュ化、あるいは、ネットワーク型データ構造を適切に利用すれば、時間計算量をＯ（１）に短縮することができる。

構文解析木比較器２１１は、すべての組み合わせに対して類似度判定基準２１３に従って、判定を下す。判定結果は、双方のブロックの組み合わせとそれ対する判定結果を比較結果リスト２１４として出力する。通常はすべての判定について比較結果リスト２１４を作成するが、場合により一部の判定に対して比較結果リスト２１４を作成してもよい。

構文解析木比較器２１１の以上の動作は図３に詳細に示している。図３に示した例では、２つの著作物Ａ、Ｂをそれぞれブロック（Ａ₁、Ａ₂、……）、（Ｂ₁、Ｂ₂、……）に分けて、類似度判定基準を使用して判定結果を比較結果リスト２１４として出力している。

類似度判定基準には、一致の程度と、それを決定する判定基準が含まれており、たとえば、次のように分類される。
（ａ）完全一致言語体系……構造、属性が一致する場合（たとえば著作権侵害検知向け）
（ｂ）部分一致言語体系……構造が一致する場合（たとえば特許侵害検知向け）
（ｃ）不一致

以上説明した本実施例では、次のような効果を得ることができる。

本実施例では、構文解析木の部分木を比較するように構成されている。このため、形式言語で記された著作物の文法構造を比較することができる。形式言語には、人工言語のほか、文法整理された自然言語も含まれるので、本実施例による応用の範囲は広い。手続き型言語、関数型言語、論理型言語パラダイム間での比較にどの程度の意味があるかは不明であるが、各言語パラダイム内での比較には、判定基準が意味をなす。自然言語であっても、形式言語であれば、著作権侵害とまでいかなくても、たとえば翻訳の文法構造が正しいかといった確認を行うことが可能である。

また、本実施例では、構文解析木によって類否を比較するので、形式言語の種類に非依存に処理が可能である。また、比較単位として部分木を用いるので、必要に応じて、トリビアルな部分木を比較対象とするか否かを調整することができ、適切な単位で比較することができる。

＜実施例の変形例＞

本発明は、以上説明した実施例そのものに限定されるものでないことは当然である。たとえば、先の実施例では構文解析木の木構造を用いた階層型ネットワークを使用したが、この構文解析木をネットワーク型データ構造で表現するようにしてもよい。これを変形例として説明する。

ネットワークデータ構造のノードは、一番上にある節としてのルート、分岐点、下に節を持たない節としてのリーフのいずれかになる。この変形例では、ルートを初期ノードとする。次に、各トークンを、解析上の出現順序に従って、付番する。これら空白やコメントを省いた認識の最小単位としてのトークンは、ノードとして扱われる。

ＸＭＬの例と対応させると、条件分岐や繰り返し、場合によっては逐次処理中に現れるブロックスコープ（statement-block相当）があれば、そこで枝分かれを行う。

条件分岐や繰り返しは、本発明の技術思想としては異なるコントロールフローという以上の違いはない。このため、いずれかの構造であることと、その分岐や繰り返しの条件のみを各ノードの属性として保持する。ただし、この変形例でネットワークデータ構造に対して行う処理の場合には、枝刈りを行ったことにより得られる各部分木は、それぞれ別のネットワークとして再認識させなければならない点に注意を要する。この結果として、各枝のすべてのノードに対応して付される一意の番号は、ルートを同じ値にして順に振り直す。

この処理に従って、ノードに接続する枝の一意の番号も再計算し、各枝に振り直すことになる。ノードと枝（ブランチ）の一意の番号を振り直すのは、取り上げたネットワーク型データ構造がその付された値に依存しているためであり、数値が一致していないと通常は異なるネットワーク構造である、と盲目的に判定してしまうためである。

したがって、この変形例の場合には、ノードと枝の一意の番号と各ノードの属性を比較することで、図２で示した構文解析木比較器２１１は類似に関して所定の判定を行うことができるようになる。

このようなネットワーク型データ構造の採用は、処理効率の悪いＸＭＬに代わるものとして期待することができる。なお、ネットワーク型データ構造の処理に際しては、これをンピュータで扱いやすい一次元的なデータ構造に置き換えることが有効である。これに関しては、たとえば本発明者の発案した関連技術（特開平１０−０７８９１１号公報）に開示された技術を利用することができる。

以上説明した本発明の実施例は、著作物の改定において構造単位での差異のリストアップといった用途にも適用できる。従来では、差分を含む行単位での差異確認のため、著作物の性格によっては、確認がわずらわしいという問題があったが、これを解消することができる。また、翻訳における文法構造チェックや、非合法に流用された著作物の文字列には依存しない構造上の同一性のリストアップといった用途にも適用可能である。

本発明の実施の形態における処理内容判定装置を使用した処理内容判定システムのシステム構成図である。本発明の一実施例による処理内容判定装置の構成説明図である。本実施例における構文解析木比較器の構成を具体的に表わした説明図である。第２の関連技術によるソースプログラム比較情報生成システムの構成の概要を表わしたシステム構成図である。

符号の説明

１００処理内容判定システム
１０１第１の比較対象記述データ格納部
１０２第２の比較対象記述データ格納部
１０３第１の比較対象記述データ
１０４第２の比較対象記述データ
１０５、２００処理内容判定装置
１０６記述ルールデータベース
１０７比較程度設定部
１０８類似判定表示部
１１１比較対象記述データ入力部
１１２記述ルール解析部
１１４類似度演算部
１１５演算結果
２０１メタ言語ソース
２０２構文解析器
２０３メタ言語
２０４第１のソース・言語
２０５第２のソース・言語
２０６第１の構文解析器
２０７第１の構文解析木
２０８第２の構文解析器
２０９第２の構文解析木
２１１構文解析木比較器
２１２比較単位基準
２１３類似度判定基準
２１４比較結果リスト

Claims

所定の関連法則を用いて組み立てられた、類似判断の比較対象となるそれぞれの記述を入力する比較対象記述入力手段と、
これら比較対象となる記述を、前記関連法則を用いてそれぞれ解析し、それぞれの記述内容を構成する記述構成内容同士の関連を表わした記述構成内容関連マップを生成する記述構成内容関連マップ生成手段と、
この記述構成内容関連マップ生成手段で生成された記述構成内容関連マップを前記比較対象となる記述同士で比較して、これらマップの一致の程度を類似度として演算する類似度演算手段
とを具備することを特徴とする処理内容判定装置。
前記所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述は、文法構造を有する記述であり、前記記述構成内容関連マップ生成手段は、比較対象となる記述をそれぞれ単一の文法構造で解析し、言語非依存な構文解析木を生成する構文解析木生成手段であり、前記類似度演算手段は前記構文解析木生成手段によって生成された比較対象となる記述同士の構文解析木を比較して、これらの構造の内容の一致の程度を類似度として演算する手段であることを特徴とする請求項１記載の処理内容判定装置。
前記所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述は、文法構造を有する記述であり、前記記述構成内容関連マップ生成手段は、比較対象となる記述をそれぞれ単一の文法構造で解析し、言語非依存なネットワークを生成するネットワーク型データ構造生成手段であり、前記類似度演算手段は前記ネットワーク型データ構造生成手段によって生成された比較対象となる記述同士のネットワーク型データ構造を比較して、これらの構造の内容の一致の程度を類似度として演算する手段であることを特徴とする請求項１記載の処理内容判定装置。
前記記述構成内容関連マップ生成手段は、前記類似判断の比較対象となるそれぞれの記述が異なる言語である場合これらを共通の言語に翻訳する前処理手段を具備することを特徴とする請求項２または請求項３記載の処理内容判定装置。
前記類似度演算手段は、比較対象となる記述の範囲を、木構造における階層の深さにより定まる比較範囲としてのブロックとして指定するブロック指定手段を具備することを特徴とする請求項２記載の処理内容判定装置。
前記構文解析木生成手段の構文解析には、手続き型の人工言語に対して、ＣＦＧ（Context Free Grammar：文脈自由文法）解析ツールを使用し、自然言語に対して、ＤＣＧ（Definite Clause Grammar：確定節文法）解析機能を持ったメタ言語を使用することを特徴とする請求項２記載の処理内容判定装置。
前記類似度演算手段の類似度の演算結果は、前記前記比較対象となる記述の一致、不一致およびこれらの中間様相を含むことを特徴とする請求項１記載の処理内容判定装置。
前記構文解析木生成手段によって生成された構文解析木を部分木の集合に分割する分割手段を供え、前記類似度演算手段は各部分木の総当りの組み合わせで比較を行って前記ブロックに対する類似度を演算することを特徴とする請求項２記載の処理内容判定装置。
所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述を入力する比較対象記述入力ステップと、
これら比較対象となる記述を、前記関連法則を用いてそれぞれ解析し、それぞれの記述内容を構成する記述構成内容同士の関連を表わした記述構成内容関連マップを生成する記述構成内容関連マップ生成ステップと、
この記述構成内容関連マップ生成ステップで生成された記述構成内容関連マップを前記比較対象となる記述同士で比較して、これらマップの一致の程度を類似度として演算する類似度演算ステップ
とを具備することを特徴とする処理内容判定方法。
前記所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述は、文法構造を有する記述であり、前記記述構成内容関連マップ生成ステップは、比較対象となる記述をそれぞれ単一の文法構造で解析し、言語非依存な構文解析木を生成する構文解析木生成ステップであり、前記類似度演算ステップは前記構文解析木生成ステップによって生成された比較対象となる記述同士の構文解析木を比較して、これらの構造の内容の一致の程度を類似度として演算するステップであることを特徴とする請求項９記載の処理内容判定方法。
前記所定の関連法則を用いて組み立てられ、類似判断の比較対象となるそれぞれの記述は、文法構造を有する記述であり、前記記述構成内容関連マップ生成ステップは、比較対象となる記述をそれぞれ単一の文法構造で解析し、言語非依存なネットワークを生成するネットワーク型データ構造生成ステップであり、前記類似度演算ステップは前記ネットワーク型データ構造生成ステップによって生成された比較対象となる記述同士のネットワーク型データ構造を比較して、これらの構造の内容の一致の程度を類似度として演算するステップであることを特徴とする請求項９記載の処理内容判定方法。