機械翻訳等の自然言語処理に必要な、 使用頻度の高い表現や固定的な言い回しなどの表現を抽出するため、 大量の言語データから、 連鎖型および離散型の共起表現を効率よく自動的に抽出するアルゴリズムを提案した。
既に、連鎖型の共起表現に対して、N-gram統計を応用した手法が提案されており、 文字列長の長い順かつ使用頻度の高い順に共起表現を抽出することが可能である。 しかし、その方法では、膨大な量の断片的で不要な表現が混在して抽出される問題があった。 そこで、本論文では、まず、抽出過程で対象文字列の有効性を判定する仕組みを考案し、 不要な表現の抽出を仰制するアルゴリズムを提案した。 次に、これによって得られた連鎖型の共起表現を組み合わせて、 離散型の共起表現を抽出する方法を提案した。
約890万字の新聞記事データに適用した例によれば、従来の方法に比べて、 断片的な文字列の抽出が抑制され、抽出される文字列の種類は20〜1%に、 またそれらの述ベ出現回数は14〜1%程度に削減されることが分かった。 また、10回以上出現した1.25万種類の連鎖型共起表現が1文中に共起する離散型の共起表現を 抽出したところ、2回以上出現したの文字列の組は6,544件であった。 以上の結果、連鎖型、離散型共に共起表現を容易に計算することが可能となり、 文型パターンなど、文構造に関する基礎データを半自動的に収集することが可能となった。
共起表現、コーパス、自動抽出、N-gram, 文型
In order to extract rigid expressions with a high frequency of use, new algorithms that can efficiently extract both uninterrupted and interrupted collocations from very large Japanese corpora have been proposed.
More recently, the technique of applying n-gram statistics for uninterrupted collocation has been proposed. This enables the extraction of collocations in the order of string length and frequency of use. But this method posed problems in that large volumes of fractional and unnecessary expressions are included. To solve this problem, this paper proposes a new algorithm that restrains the extraction of unnecessary expressions. This is followed by the proposal of a method that extracts interrupted collocations combining the uninterrupted collocations thus obtained.
These new methods are applied to newspaper articles containing 8.92 million characters. In the case of uninterrupted collocations with string length of 2 or more characters and whose frequency of appearance is 2 or more times, there were 4.4 million expressions (total frequency of 31.2 million times) extracted by the conventional method. In contrast, the new method reduced this to 0.97 million types (totaI frequency of 2.6 million times) revealing a substantial reduction in fractional and unnecessary expressions. In the case of interrupted collocatjonal substring extractions, combining the substring with frequency of 10 times or more extracted by the first method, yielded 6.5 thousand types of pairs of substrings with the total frequency of 21.8 thousand times,
Collocation, Corpora, Automatic Extraction, N-gram, Sentence Pattern
| 1. まえがき | |
| 2. 従来の方法とその問題点 | |
| 3. 連鎖型共起表現の抽出法 | |
| 3.1 重なる文字列の扱い | |
| 3.2 文字列抽出アルゴリズム | |
| 4. 離散型共起表現の捕出法 | |
| 4.1 抽出する共起文字列の条件 | |
| 4.2 文字列抽出アルゴリズム | |
| 5. 共起表現の抽出実験 | |
| 5.1 連鎖型共起表現の抽出 | |
| 5.2 離散型共起表現の抽出 | |
| 6. あとがき | |
| 参考文献 |
最近、自然言語処理において、大量のコーパスや用例の重要性が指摘され、 それを分析する技術の必要性が増大している。 例えば、機械翻訳では、単語単位の直訳ではうまく訳せないフレーズを集め、 フレーズ単位に翻訳する方法や、表現の構造をパターンとして辞書に登緑し、 その辞書を用いて翻訳する方法などが考えられている。
これらの方法を実現するには、現実に使用されている言語データの中から、 使用頻度の高いフレーズや表現のパターンを発見し、抽出する必要がある。 従来、言語データから結びつきの強い単語を取り出す方法として、 2単語の結びつきの強度に着目した方法(1)、 単語間の距離に着目した方法(2)、 結合単語数と出現回数を考慮した 方法(3,4)などが提案されている。 しかし、大量の言語データから、任意の長さで、出現頻度の高い表現を自動的に発見して、 抽出することは困難であった。 そのため、抽出する単語や文字の連鎖の数を限定する方法や、制限された範囲で、 連鎖の数を増やして集計する方法(5)などが考えられていた。
これに対して、最近、大量の言語データを対象に、 任意の数nに対するn-gram統計を高速に実行する方法が 提案された(6)。 この方法を用いれば、原文中に使用された文字列を、 その長さ(文字数)の順かつ出現頻度の順に抽出し、集計することが出来る。 しかし、この方法では、抽出する文字列間の相互関係が無視されている。 そのため、既に抽出された文字列の部分文字列が重複して抽出される。 すなわち、文法的、意味的にまとまりのない断片的な文宇列が多数抽出される。 これを意味のある文字列に絞り込む方法として、 抽出した文字列のエントロピー基準を用いる方法(7)や 助詞的定型表現に限定していくつかのヒューリスティックスを用いる 方法(8)などが提案されているが、 独立した表現の単位となるような文字列を漏れなく選択するのは容易でなかった。 また、抽出された文字列の出現回数には、 その文字列を含むより大きな文字列の出現回数が含まれるため、 出現頻度表から、各文字列が独立して出現した回数を求めることは出来なかった。
次に、離れた位置に共起する表現の組(離散型の共起表現)を抽出するためには、 複数の文字列を組み合わせて原文をサーチすることが必要である。 連鎖型、離散型を特に区別せず、 1文中に共起表現が占める割合の多い文を定型的な文として抽出する 試み(9,10)もあるが、 大量の言語データの中から、出現頻度の高い文字列の組を、 漏れなく自動的に発見し集計するのに効果的な方法は知られていない。
本論文では、これらの問題点を解決するため、言語データの中から、 文字列を、それらが部分文字列として相互に重複するものは対象外とすると言う条件の下で、 文字数の多い順、かつ使用頻度の高い順に、漏れなく、自動的に抽出し、集計する方法を提案する。 また、その結果を使用して、離散型の共起表現を自動的に抽出し集計する方法を示す。
(1) 文字列抽出の条件
自然言語表現に共起する表現には以下の2種類がある。 第1は、連語やフレーズのように連続した文字列を構成するもの(連鎖型共起表現と呼ぶ)であり、 第2は、係り結び、呼応関係、特定の動詞と特定の名詞の組などのように、 2種以上の文字列が、文中の離れた位置に現れるもの(離散型共起表現と呼ぶ)である。 離散型共起表現は、連鎖型共起表現の文字列が文中で、 共起したものと考えることができるから、まず、第1の文字列を考える。
さて、連語やフレーズのような連続した文字列を漏れなく発見すること、 また、文法的、意味的に見て、 表現の単位をなさないような断片的な文字列の抽出を最小限に押さえることを狙って、 以下の条件で文字列を抽出することとする。
| 第1の条件: | 一致文字数(文字列長)の大きい順に抽出する。 |
| 第2の条件: | 出現頻度の高い順に抽出する。 |
| 第3の条件: | 最長一致の原則で文字列を 抽出する*1。 |
上記の条件を満たす方法を考える前に、基本となる長尾・森の方法について考察する。
[長尾・森の方法]
手順1: 原文番地ファイルの作成
原文データの文宇数を文字数をNとし、原文データの先頭文字から順に、 0, 1, 2, 3, ・・・N-1の文字番地を付与する。 原文番地i(＝0, 1, 2, ・・・, N-1)で始まり、 末尾の文字(N-1番地)で終わる部分文字列を文宇列単語iとすると、N個の文字列単語ができる。 このようにして作成された文字列単語の番号をレコードに持つファイル (原文番地ファイル)を作成する。 (単純に言えば、レコード数Nのファイルを作り、各レコードに0からN-1までの数記入する。)
手順2: 汎用ソートファイルの作成
原文番地ファイルのレコードで示される文字列単語iを文字コードの順にソートする。 得られたファイルを汎用ソートファイルと呼ぶ。
手順3: 一致文字数のカウント
汎用ソートファイルのj番目のレコード(J=0, 1, 2, ・・・N-1)で表される文字列単語と、 j+1番目のレコードで表される文字列単語の文字を先頭から比較して、 一致する文字数を、レコードjの別フィールドに書き込む。
手順4: 文字列の抽出とカウント
汎用ソートファイル上の先頭レコードから順に、隣り合う一致文字数の値を比較し、 抽出文字列とその出現回数を求める。
この方法により、第1、第2の条件は満足されるが、目標とする第3の条件は満足されない。 第3の条件を満たすためには、抽出された文字列の出現回数に対して、 より長い文字列に含まれていた部分文字列の出現回数を差し引けば良いと考えられるが、 それでは正しい答えは得られない。 すなわち、集計表の生成された時点では、 抽出された文字列の原文中での相互関係の情報が失われているため、 計算は不可能である*1。
第3の条件を漢足させるため、2つの文字列、すなわち、 n-gram文字列とm-gram文字列の抽出を考える。 問題となるのは、図1に示すように、両者に何らかのオーバーラップがあるときである。
|
|
(1) 一方が他方を内包する場合
この場合は、さらに3つの場合に分けられるが、いずれの場合も、 m-gram部分はn-gramとして抽出された文字列の部分に包含されるので、抽出の対象とならない。 従って、n-gram文字列を抽出するとき、n-gram文字列として抽出した文字列の部分は、 後の処理でm-gram文字列の対象としないよう 「汎用ソートファイル」の該当レコードを無効化する必要がある。
(2) 互いに部分を共用する場合
この場合は、図のように、さらに2つの場合に分けられるが、 いずれの場合も、m-gram文字列とn-gram文字列は、 原文上互いにその一部を共有するだけであるので、抽出対象文字列である。
(1) アルゴリズム
前章の議論をふまえ、原文データから、 2回以上の出現回数を持つ固定的な(連続した)表現を文字列として、 文字数の多い順に、かつ、重複なしに抽出するアルゴリズムを提案する。
＜前準備＞
まず、長尾等の方法で使用された「汎用ソートファイル」を拡張し、 その各レコードに、「抽出文字数」の欄を設ける(図2参照)。
＜文字列抽出アルゴリズム＞
手順1〜手順3: 長尾等の方法と同じ
手順4: 「抽出文字数の記入」
上記で得た「拡張汎用ソートファイル」上の「抽出文字数」の欄に、 自分のレコードの文字列単語は、先頭から何文字までが抽出対象となっているかを記入する。 具体的には、レコードを先頭から順に見て、自分のレコードの一致文字数の値が、 直前のレコードのそれと同一の値か、それより大きい値の場合は、一致文字数を抽出文字数とする。 逆に、自分のレコードの一致文字数の値が直前のレコードの一致文字数より小さいときは、 直前のレコードの一致文字数を自分のレコードの抽出文字数とする。
手順5: 「拡張原文番地ファイルの作成」
手順4で得られた拡張汎用ソートファイルを原文番号順に再ソートしたあと、 各レコードに「採否表示」の欄を設け、それを「拡張原文番地ファイル」とする。
手順6: 「有効無効判定処理」
拡張原文ファイル上で、以下の方法で、先頭レコードから順に、各レコードの無効判定を行い、 その結果を、「採否表示」欄に記入する。
すなわち、先頭レコードから「抽出文字数」の値を調ベ、iレコード目で、 始めて0でない値nを発見したとする。そのとき、i番目のレコードの採否表示は「〇(採用)」とし、 それに続くi+1, i+2, ・・・, j+(n-1)のレコードの抽出文字数の値を調べる。 それらの値が、 それぞれ、n-1, n-2, ・・・, 1以下であるレコード採否表示を「×(不採用)」とし、 それ以外のレコードの無効表示は「〇」とする。 次に、新たに「〇」と判定されたレコードの番号をiとして、同様の処理を繰り返す。 「〇」と判定されたレコードのないときは、i+nのレコードまで進む。 そのレコードの「抽出文字数」0の時は、はじめと同様、0でない値を持つレコードまで進み、 同様の手順を繰り返す。
手順7: 「再拡張汎用ソートファイルの作成」
上記で得られた「拡張原文番地ファイル」を再度、 「汎用ソートファイル」レコード順にソートし、「再拡張汎用ソートファイル」を作成する。
手順8: 「抽出文字列集計処理」
「再拡張汎用ソートファイル」を参照して、以下の手順で、抽出する文字列を決定し、 同時に、その出現回数を求める。
| �� | 採否表示が「〇」となっているレコードを調べ、 抽出文字数の最大のレコードを探す。 そのレコードの一致文字数をnとする。 |
| �� | 抽出文字数の値がnの最初のレコードの番号をi1とすると、 i1からから始まって、後方のレコードを見たとき、 抽出文字数が連続してnとなるレコードの数が、そのn字の文字列の出現回数であるから、 文字列と出現回数(但し、出現回数2以上)を集計表に記録する。 次に現れた、抽出文字数がnのレコードi2に対して、 前と同様にして文字列と出現回数を集計表に記緑する。 |
| �� | n＝n-1とし、�△亮蟒腓魴�り返す。n＝0になったら処理は終了する。 |
(2) 例題検討
以上のアルゴリズムの適用例を図2に示す。 この例では、従来のアルゴリズムで抽出される文字列の種類が24種類で、 延べ抽出文字列数が72件であったのに対して、本論文の方法では、5種類、10件に絞られる。
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
離散型共起表現の種類と出現回数を求める方法として、原文データを先頭の文から順にサーチし、 3章の方法で抽出された文字列の2つ以上の組が一文中に現れる現象を、 文字列の組毎にカウントすることを考える。 一文中に現れる表現が対象となる点から、文境界文字(句点)の扱いが問題となる。 また、離散型の共起を拾い出す点から、抽出する表現の位置関係が問題となる。
(1) 句点の扱い
一文内の文字列の共起を考えると、句点にまたがる表現は、集計の対象外と考えて良い。 しかし、引用文等、一文内に句点を持つ別の一文を内包する文では、 文単位の取り出しが単純ではなくなる。ここでは簡単のため、 文中に引用記号(括弧など)が発見された時は、 その引用記号と対になる引用終了記号(閉じ括弧など)が発見されるまでは、 句点を無視することとする。
(2) 抽出する文字列の相互関係
離散型の文字列共起の抽出では、文中で、 互いに接続した文字列や部分的にオーバーラップする文字列は抽出の対象外となる。 例えば、文字列αとβが同一の文から抽出されたとする。 その位置的関係は、図3に示すような3つの関係のいずれかとなる。 このうち、文字列αとβが分離している場合(c)が、分離型共起表現の抽出対象であり、 (a)、(b)は対象外である。
|
(3) 文字列の出現順序
離散型共起表現では、その部分的文字列の出現順序が問題になるから、 文字列の前後関係を分けて共起文字列の抽出とカウントを行う。
(1) アルゴリズム
[前準備]
文内の離散型の共起文字列の抽出に先だって、3章のアルゴリズムに以下の処理を追加する。
| (1) | 手順3の文字列抽出で、句点(”。”)にまたがる文字列は抽出しない。 |
| (2) | 「再拡張汎用ソートファイル」に「文字列番号」の欄を設ける。 |
| (3) | 手順8の処理で最終的に抽出された文字列の組に対して、抽出の順に文字列番号を付与し、 該当するレコードの「文字列番号」欄にその番号を入れる。 |
手順9: 「再拡張汎用ソートファイルの再ソート」
「再拡張汎用ソートファイル」を原文番地の値の順にソートし、 「拡張原文番地ファイル」の形式に戻す。
手順10: 「文番号の付与」
手順9で得られたファイルに、「文番号」欄を設け、 自分のレコードが所属する原文上の文番号を記入する。 文番号の記入は、4.1章(1)で述ベた点に注意して行う。
手順11: 「ファイルの圧縮」
手順10で得たファイルを以下の手順で圧縮し、「離散型共起圧縮ファイル」を作成する。
| �� | 「文番号」、「文字列番号」、「抽出文字数」、 「原文番地」の4つの欄以外は、削除する。 |
| �� | 「文字列番号」の欄の値がないレコードを削除する。 |
手順12: 「離散型共起表現の抽出とカウント」
抽出された文字列の番号を縦軸、 横軸に並ベたマトリックス型の「離散型共起データ表」を作成する。 着目する文字列を順に定め、その文字列と共起する文字列を、 「離散型共起圧縮ファイル」上で探して、共起データ表の該当する欄にその回数を加える。 すべての行に対して、「離散型共起圧縮ファイル」が 各1回サーチされる*1。
手順13: 「2度数以上の共起表現の集計」
「離散型共起データ表」の度数2以上の表現の組を取り出して、 「離散型共起文字列集計表」を作成する。 これが最終的な、集計結果である。
手順14: 「3種類以上の文字列の共起の場合」
3種類の文字列の共起の場合は、手順13で得られた文字列の組の内、 着目する組を、「離散型共起文字列集計表」の横方法に並べ、手順12と同様の処理を行えばよい。 4種類以上の表現の共起に場合は、さらに、一つ手前の集計結果を縮退同様の処理を繰り返す。 但し、2種類の文字列の共起では、着目する文字列の文中での出現順序を考慮した集計とした。 また、3種類以上の文字列の共起では、場合の数が増大するため、 文字列の出現順序は意識しないこととする。
以上で、離散型共起表現の集計表が求められるが、 さらに、それらの表現を含む文を出力するには、次に手順によればよい。
手順15: 「離故型共起文例の出力」
出力すべき文例を、手順14で出力された共起表現の番号の組で選択して、 離散型共起圧縮ファイルをサーチし、該当する部分の文を出力する。
(2) 例題検討
以上の手順を、図2の例に適用した結果を、図4に示す。 この例では、3章で抽出された5種の連鎖的共起文字列の組(25組)の中で、 1文内文に離れて2回以上、共起する文字列の組が7組で、それらの延べ出現回数は14回である。
図4 離散型共起表現抽出アルゴリズム実施例(図2の手順7から続く)
5. 共起表現の抽出実験日経産業新聞記事3ケ月分(892万字)を対象に、連鎖型共起文字列の抽出実験を行った。 その結果を、表1〜4に示す。使用した計算機は、SUN(OS4.1.3)で、 使用したメモリ量は、最大48MBである。 5.1 連鎖型共起表現の抽出2回以上出現した文字列及び2文字以上の文字列に対して抽出された文字列の種類数と 延べ出現回数をそれぞれ表1、表2に示す。 また、実際に抽出された文字列の例を表3、出現頻度の高い文字列の上位何件かを表4に示す。
表1 抽出された文字列の種類と頬度(その1)
表2 抽出された文字列の種類と頻度(その2)
表3 抽出された文字列の例(10gramの例)
表4 出現頻度の高い文字列の例
これらの表から、以下のことが分かる。
処理時間では、最初の文字列単語のソート(汎用ソートファイルの作成)に、 最も多くの時間(数十時間)がかかったが、その後の処理は、それに比べて短時間(約30分)であった。 5.2 離散型共起表現の抽出連鎖型共起文字列として単独では10回以上出現した12,351件を対象として、 このうちの2種類の文字列が1文内に離れて共起する場合を集計した。 抽出された文字列の組の数を表5に, 出現頬度の多い文字列の組を表6に, 2回以上出現した文字列の組のうち合計文字数の多い文字列の組を表7に示す。
表5 抽出される文字列の組の種類と延べ度数
(2種類の文字列の文内共起の場合)
表6 出現頬度の高い文字列の組の例
表7 合計文字数の大きい文字列の例
これらの表から、出現順度の高い離散型共起は名詞同士の共起が圧倒的に多いことがわかる。 抽出された表現の組は2度数以上が6,544件であるので, 人手により目的に応じた表現の組を取り出すのが可能であると思われる。 しかし, 抽出対象の表現の範囲を予め指定すれば, 離散型共起表現は能率的に抽出される。 例えば, 表現上の言い回しに着目して共起表現を抽出するには, 手順8で得られた連鎖型共起表現の中で不要と見られる表現を削除した後, 手順9以降の処理を行なえばよい。 そこで, 固有名詞や数詞を含む文字列を除去した残りの文字列に対して離散型共起を求めた。 その一部を表8に示す。 表から新聞記事の文型に相当するような離散型共起表現が抽出されることがわかる。
表8 抽出された離散型共起表現の例
なお, 本方式では, 原文データは文字列として扱い, 2文字以上の文字列複数個が文内で共起する場合を対象としたが, 共起する文字列が1文字の場合にも文法的に重要な意味を持つ場合が考えられる。 そのような場合は文字列に対する処理では限界が考えられるので, 原文データを形態素解析した後, 形態素列に対して本稿の方法を適用するなどの改良が有効であると考えられる。 6. あとがき言語コーパスなどの膨大な言語データの中から、 使用頻度の高い表現及び表現の組を自動的に発見し集計する方法を提案した。 具体的には、まず、任意のn-gramの計算法として提案された長尾等のアルゴリズムを改良し、 言語データの中に2回以上出現した文字列(連鎖型共起表現)を、 相互に部分重複のあるものは対象外とすると言う条件下で、文字数の多い順、 かつ使用頻度の高い順に、漏れなく、自動的に抽出し、集計する方法を提案した。 次に、この方法で抽出された文字列を組み合わせて、 文中の離れた位置に共起する文字列の組(離散型共起表現)を抽出し、 その頻度を求める方法を示した。 約890万字の新聞記事データに適用した例によれば、従来の方法に比べて、 断片的な文字列の抽出が仰制され、抽出される文字列の種類は20〜1%に、 またそれらの述べ出現回数は14〜1%程度に削減されることが分かった。 また、10回以上出現した1.25万種類の連鎖型共起表現が 一文中に共起する離散型の共起表現を抽出したところ、 2回以上出現したの文字列の組は6,544件であった。 これから、固有名詞や数詞などを除去すれば, 新聞特有の表現形式が抽出できる。 以上の結果、連鎖型、離散型共に共起表現を容易に計算することが可能となり、 文型パターンなど、文構造に関する基礎データを半自動的に収集することが可能となった。 本論文では、日本語文字列への適用を考えた。 しかし、この方法は、任意の記号列に適用できる。 単語単位に分割した単語列や形態素解析結果得られた文法的要素列、 もしくは、各単語をその意味属性で置き換えた意味属性連鎖など、種々の応用が可能である。 文字列への適用では、まだ若干の断片的文字列が出力され、 それが、離散型共起の計算の負荷を重くしているが、 単語列や文法的要素列への適用では、よりごみの少ない結果が期待される。 これらの点を考えて、今後は、種々の適用実験を行い、さらに改良を加えていくつもりである。 参考文献
Footnote *1 すなわち、原文中のある場所からある文字列が抽出されたとき、 その文字列内に含まれる部分文字列は抽出の対象としない。 但し、その部分文字列が別の場所に現れた時は抽出される。 (Return) *1 従来、単語列の場合、ある単語列αの出現頻度を、その単語列の出現回数がら、 それを含むより大きな単語列βの出現回数を引くことにより評価する方法が使われていた 例(3)もあるが、厳密には、 この方法では正しい結果は得られない。 (Return) *1 手順12以降では、出現回数をマトリック上で積算する方法法としたが、 マトリックスがスパースになるときは、ファイル吐き出しの方法が良い。 その場合は、共起した出現した表現の番号を組にしてファイルに吐き出し、 後で、ソートして同一の組の数をカウントすればよい。 (Return) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||