英文法律関連テキストを対象とした文境界推定の論文を読む

はじめに

法律ドメインに特化した自然言語処理は、ビジネス上重要な位置を占めるにもかかわらず、金融や医療等の他の分野と比べいままであまり重きをおかれることがなかった分野でした。

法律関連のタスクに電子機器が使われる機会は徐々に高まっており、自然言語処理を応用し、法律の実務家や法律関連SaaSのユーザに価値を提供する機会もまた増えてきています。

このような状況の中で、自然言語処理の研究者と法律の実務家が一堂に会する機会を設けるためにNLLP (Natural Legal Language Processing)ワークショップが設立されました。 今年はCovid19の影響でバーチャル開催され、KDD(Knowledge Discovery and Data Mining)と同時期に行われています。

sites.google.com

本記事ではNLLP 2019で発表された論文：Sentence Boundary Detection in Legal Text を元にドメイン特有の文境界推定(Sentence Boundary Detection : SBD)の手法を見ていきます。

www.aclweb.org

文境界推定について

日本語書き言葉の場合は句読点のおかげであまり問題にはならないかもしれませんが、英文テキストについては文境界推定は重要な自然言語処理タスクの一つとされています。

例えば、文中にピリオドがない通常の英文ではピリオドで文の境界を決定できますが、ピリオドを含むような要素が文に含まれている場合、文境界の決定は困難なものになります。

• 文書タイトル : UNITED STATES of America, Plaintiff– Appellee, v. Matthew R. LANGE, Defendant–Appellant.
• リスト: 1. The Veteran does meet the criteria for a diagnosis of posttraumatic stress disorder (PTSD).

他のドメインのテキストでは文境界決定タスクはほとんど解かれているというのが定説ですが、法律ドメインのテキストは法律ドメインならではの難しさがあります。

法律文書における文境界推定の困難さについて

文境界推定が法律ドメインのテキストに対して特に困難なのは、それらが構造化された節や前文、後文から成っており、新聞記事のような解説文でないためです。

以下に法律ドメインのテキストに特有の文構造を列挙します。

要素	テキスト例
文書タイトル	UNITED STATES of America, Plaintiff– Appellee, v. Matthew R. LANGE, Defendant–Appellant.
見出し	ARGUMENT INTRODUCTION I. BACKGROUND
フィールドと値	DOCKET NO. A–4462–13T2
ページ番号	*1163 See United States v. Pina-Jaime, 332 F.3d 609, 612 (9th Cir.2003)
省略記号（...）	...After granting discretionary review, the Supreme Court, Aker, J., held that rule, which stated that court
括弧書き	see also United States v. Infante-Ruiz, 13 F.3d 498, 504- 505 (1st Cir.1994) (when third party consent to search vehicle and trunk is qualified by a warning that the briefcase belonged to another, officers could not assume without further inquiry that the consent extended to the briefcase)
数え上げリスト	FINDINGS OF FACT 1. The Veteran does meet the criteria for a diagnosis of posttraumatic stress disorder (PTSD).
注釈	and three counts of possession of device-making equipment, 18 U.S.C. § 1029(a)(4).[2]
文中参照	Thus, even an “infinitesimal contribution to the disability might require full contribution.” (Id., at pp. 430–431, 133 Cal.Rptr. 809.) The Heaton court also rejected this argument, noting that section 31722 explicitly provided for mental as well as physical disabilities.

このような特殊な文構造には重要な情報が含まれることも多く、後続の文単位での情報抽出などがある場合には、その抽出精度に間接的に影響します。

法律ドメインのテキストを時系列モデルの学習器を使って学習させることで、これらドメインに特有の表現を考慮した文境界推定をより正確にできるようにしたのが本論文の概要になります。

検証方法

論文中では米国裁判所での判決文のデータセットjsavelka/sbd_adjudicatory_decに対し、下記の対応のように形態素ごとに文の頭か B 文中か I 文末か L のタグがアノテーションされたデータを生成します。

そして、下記の判定モデルを用いてタグ判定を行っています

• Punktモデル : 自然言語処理ライブラリnltkに含まれるPunktSentenceTokenizerを用いたモデル（未学習/学習状態で精度を算出）
• 条件付き確率場モデル(CRF)：各形態素から取得できる前後含む特徴量（後述）とBIOタグを用いて学習したモデル。sklearn_crfsuiteを利用
• 双方向LSTMモデル(Bi-LSTM) : 各形態素から取得できるword2vec特徴量にCRFモデルで用いたような特徴量を加えたものを元に学習したモデル。

CRF、Bi-LSTMで用いられる代表的な特徴量としては下記のようなものが用いられています。Appendixに詳細が記載されています。

• length : 文字列長、ただし4-6の場合normal, 6以上の場合long
• islower : 形態素がすべて小文字か
• isupper : 形態素がすべて大文字か
• istitle : 形態素先頭のみ大文字で他がすべて小文字か
• isdigit : 形態素がすべて数字か

検証結果

以下論文からの抜粋で、上から順に未学習Punktモデル, 学習済みPunktモデル、CRFモデル、Bi-LSTMモデルの結果になります。

Iタグは全体として数が多いため、比較対象としてIタグを除いたBLタグのみでの加重平均が赤字で記載されています。

ベースラインのPunktモデルとCRF、Bi-LSTMを比較するとPunktモデルの学習前後と比較してCRF、Bi-LSTMモデルは適合率についてPunktモデルより10ポイント以上の向上が見られます。

一方でCRFとBi-LSTMモデルにそこまで目立った差異はないように見られます。論文中では適合率についてCRFのほうが若干高めということで一番Performしたモデルと記載がありそれは確かにそうなのですが、CRFのモデルは比較的ヒューリスティックな特徴量を用いている関係もあって、word2vecで作成した特徴量のモデルと単純に比較できない側面もあるかなとは感じました。

おわりに

文章をどのような位置で区切るかという問題については仕事でも考える機会があり、どのような特徴量を取るかという部分については非常に参考になりそうな論文でした。

広告

この記事はMNTSQ勤務中に書かれた。

MNTSQは自然言語処理と法律に関心のあるエンジニアを募集しています。

www.wantedly.com

ブートストラッピング法による情報抽出の論文まとめ

はじめに

自然言語処理におけるタスクの一つとして、構造化されていないテキストから情報や知識を自動または半自動で取り出すことを情報抽出といいます。

最近では深層学習系の論文が国際学会ではメジャーですが、訓練・ベンチマークに用いているデータセットのレコード数が膨大であり、また高価なGPU環境が言語モデルの訓練のために必要など、必ずしも現実の要件で扱われる問題と合致していない部分があります。

また、抽出の際に起こる問題や、抽出の際に用いる指標を古典的な手法を通じて押さえておくことで、実際のデータに既存手法や経験的な手法をいろいろ適用してみるときの手がかりになります。

そこで本記事では情報抽出の領域で深層学習が流行る前に比較的メジャーであったブートストラッピング法にフォーカスし、抽出の概念、手法の解説、論文のタスクや手法の詳細などを追っていきます。

論文の流れを追うことで情報抽出の応用をしようとしている人にとって何らかの示唆があれば幸いです。

情報抽出について

構造化されていないテキストから情報や知識を自動で取り出す。とはどういったことでしょうか。

例をいくつか上げてみます。

例えば新聞記事のテキストがあった時に、企業名と本社の場所を対で拾いたいとします。

・XXX社（本社：東京都中央区）は18日、新製品を発売すると発表した。

・東京都千代田区のYYY社の取締役、〇〇氏は…

この場合、対で拾いたい情報は以下の通りです

会社名	本社所在地
XXX社	東京都中央区
YYY社	東京都千代田区

また、Web上の膨大なドキュメントの中から本のタイトルと著者名を拾いたいとします。

・『ハリー・ポッター』（英: Harry Potter）は、イギリスの作家J・K・ローリングによる児童文学、ファンタジー小説のシリーズ。

・アイザック・ニュートンの代表作『プリンシピア 自然哲学の数学的原理』は出版当時から難解と言われた。

この場合、対で拾いたい情報は以下の通りです

本のタイトル	著者名
ハリー・ポッター	J・K・ローリング
プリンシピア 自然哲学の数学的原理	アイザック・ニュートン

例として上げたような、情報抽出の対象が「会社名と本社所在地」「本の著者」などといった2つの固有名間の関係を抽出するものである場合、これを関係抽出（Relation Extraction）といいます。

情報抽出の対象が一つの固有名や3つ以上の固有名であるケースもあります。抽出対象が固有名一つの、「会社名」「組織名」「人名」のようなものになる場合、これを固有表現抽出と呼んだりします。

情報抽出、固有表現抽出に関する概念の整理は以下の書籍の一章に更に詳しい解説が載っています。

情報抽出・固有表現抽出のための基礎知識 (実践・自然言語処理シリーズ)

ブートストラッピング法について

自然言語処理の情報抽出におけるブートストラッピング法¹は、人手によるタグ付け作業を軽減するためのフレームワークです。

例えば関係抽出として<本のタイトル、本の著者>を取得するタスクを考えてみます。

ブートストラッピング法に於いてはこの<本のタイトル、本の著者>を表したペアをインスタンスとよび、インスタンス周辺にあるペアの手前、中間、後ろにある形態素を元に構成される周囲の情報をパターンとよびます。

ブートストラッピング法では以下の流れで抽出対象のテキストからインスタンスを抽出します。

1. シードインスタンスの用意：初めにインスタンスの集合として何種類かのパターンを用意する。
2. インスタンス事例探索：手元のインスタンスを元に、インスタンスが出現した部分（インスタンス事例）を洗い出す。出現した部分は、後のパターンの抽出に用いるため、文脈情報として一時的に保管しておく。
3. パターンの抽出：2で抽出した文脈の情報をもとに、パターンを抽出する。
4. インスタンスの抽出：3で抽出したパターンを用いてインスタンスを抽出する。
5. インスタンス数判定：抽出できたインスタンスの量が十分であれば終了。そうでなければ手元のインスタンスを更新した上で2のプロセスに戻る。

図にすると以下の通りです。

インスタンス抽出のイテレーションが進むに従って、シードインスタンスで想定した関係とは異なる関係を持つインスタンスが抽出されることがあり、これを意味ドリフトと言います。

個別の論文では、意味ドリフトを防ぐため、この図に加えてさらに判定材料が加わります。具体例については論文のセクションで見ていきます。

論文

Extracting Patterns and Relations from the World Wide Web (1999)

• Sergey Brin, Extracting Patterns and Relations from the World Wide Web (1999)

書籍の著者とタイトルを抽出するタスクを取り扱っており、手法としてDual Iterative Pattern Relation Extraction（DIPRE）を提案しています。DIPREはほぼブートストラッピング法なのですが、パターンの生成方法に工夫があり、パターンの特殊性（Specificity）を用いてパターン抽出の量を減らすことで、意味ドリフトの問題を克服しようとしています。

DIPREにおけるインスタンス事例とパターンの属性

DIPREにおけるインスタンス事例(Occurrence)は、以下の7つの要素を持つタプルで構成されます。

• author : 著者
• title : タイトル
• order : 著者→タイトルかタイトル→著者か
• url : 記事のURL
• prefix : 著者の手前m文字（orderがFalseならタイトル手前m文字）
• middle : 著者とタイトルに挟まれた文字
• suffix : タイトルの後m文字（orderがFalseなら著者の後m文字）

また、パターンは以下の5つの要素を持つタプルになっています。

• order: パターンの想定するorder(インスタンス事例のorderに対応)
• middle: 著者とタイトルに挟まれた文字
• urlprefix: 記事のURLの探索範囲（prefixのため、初めの部分がマッチしているURLについてインスタンス抽出の対象になる）
• prefix: インスタンスの手前文字マッチ対象
• suffix: インスタンスの後の文字マッチ対象

パターンの生成

インスタンス事例を用いて、ブートストラッピング法における「3.パターンの生成」は以下のようにして行われます。

• インスタンス事例に対して走査を実施し、orderとmiddleの一致を確認できたものでグルーピングし、パターンを作成します。作成したパターンのorder, middle属性とします。
• 作成したパターンに該当するインスタンス事例全体に対してurl属性を走査し、プレフィックスとして最長のものをパターンのurlprefix属性とします。
• prefix, suffixも同様に最長のものをパターンのprefix, suffix属性とします。

URL, prefix, suffixを最長のものをとることによって、できるだけ次のインスタンス抽出時に取得する対象のインスタンスを限定しようとしています。

パターンの特殊性

更にDIPREではパターンの生成に際し、パターンの特殊性(Specificity)を考慮しています。パターンの特殊性にはいろいろな測定の仕方がありますが、計算効率化のため、以下のSpecificityを用いています。(ここで $| \cdot |$ は文字列の長さを表す)

\text{Specificity}(p) = |p.\text{middle}||p.\text{urlprefix}||p.\text{prefix}||p.\text{suffix}|

DIPREではこのSpecifityが低いものを一定のしきい値で省くようにし、抽出されるパターンの品質を担保するようにしています。（実際にはもう少し込み入った評価の仕方をしていますが、ここでは省きます）

除外パターンの回復

さらに、Specificityで除外されたパターンについても以下のようなプロセスでできる限りパターンを抽出するプロセスが走ります。

1. URLについてグループのインスタンス事例がすべて同じURLをもつ場合はパターンの候補として除外
2. そうでない場合はURLからurlprefixを除外した部分を用いて再度グルーピングを実施する。それらをサブグループとして扱ってパターン抽出のプロセスを再帰的に実施

このような過程を経て得られたパターンを用いて、ブートストラッピング法のプロセス「5.インスタンス数判定」に移り、インスタンス数が不十分な場合には2の段階に戻ります。

Snowball: Extracting Relations from Large Plain-Text Collections (2000)

• Eugene Agichtein, Luis Gravano, Snowball: Extracting Relations from Large Plain-Text Collections (2000)

DIPREをベースに、パターン抽出、インスタンス抽出の際に固有表現タグや前後のパターンをベクトル化したものでマッチ度合い（Degree of Match）を測定することで意味ドリフトを回避しようとしています。また、パターン、インスタンスに対する確信度を計算することで、インスタンスの抽出の対象として確実なものを取得するようにしています。

マッチ度合い

パターン抽出の際に、SnowballではDIPREの方法に加えて、パターンの持つ属性として、固有表現のタグも追加するようにします。例えば、「会社名と本社所在地」の例でいうと、これまで会社名に該当するパターンにはどのような品詞もインスタンスの片方の要素として追加できたのに対して、Snowballでは会社名に該当する位置に固有表現タグで必ず＜組織名＞がつくインスタンスのみを抽出するようなパターンが生成されます。

DIPREではorderとmiddleの一致性によってインスタンス事例をグルーピングしていましたが、Snowballではマッチ度合い(Degree of match)という概念を導入し、マッチ度合いを類似度に見立てた単連結クラスタリングをすることでインスタンス事例のグルーピングを行います。この時、マッチ度合いはprefix, middle, suffixそれぞれの文脈情報をベクトル化した値を元に計算されます。

以下 $l_P, m_P, r_P$ 等はprefix, middle, suffixの文脈を表すベクトルとし、$t_P = <l_P, m_P, r_P>, t_S = <l_S, m_S, r_S>$ をインスタンス事例の前後文脈を表す値とします。するとマッチ度合いは

\text{Match}(t_P, t_S) = \begin{cases} l_P \cdot l_S + m_P \cdot m_S + r_P \cdot r_S &\text{if the tags match} \\\\ 0 &\text{otherwise} \end{cases}

のように計算されます。

グループ内にあるインスタンス事例のprefix, middle, suffixを表すベクトルのセントロイド（平均したもの）が最終的なパターンの出力として用いられます。つまり、Snowballにおけるパターンの表現はprefix, middle, suffixを表すベクトルのセントロイドを $\bar{l} _ s, \bar{m} _ s, \bar{r} _ s$ インスタンスを構成する固有表現タグを $t_1, t_2$ として

< \bar{l}_s, t_1, \bar{m}_s, t_2, \bar{r}_s >

とできます。

マッチ度合いの概念はインスタンス抽出の際にも用いられ、コンマや限定詞（a, his, this等）のブレが文脈の中にあってもインスタンスを抽出できるようになっています。

確信度の計算

パターン抽出、インスタンス事例抽出を繰り返していく中で間違ったインスタンス事例を抽出しやすいパターンも出てきます。例えば

Intel, Santa Clara, announced...

のようなテキストから取れるパターンは middle の文脈を表すベクトルが $<",", 1>$ で構成され、このパターンを用いると <組織名>, <場所> で構成されるテキストすべてにマッチします。このようなパターンを用いて生成されたインスタンス事例は信用ができないため、それを測定するためにSnowballでは確信度(Confidence)を導入しています。

確信度はまずパターンに対して算出されます。Snowballで抽出してきた手元のインスタンスと合致する組をパターンが算出すればするほど確信度が高くなるように次の式を用います。

\text{Conf}(P) = \frac{P.\text{positive}}{(P.\text{positive} + P.\text{negative})}

ここで、$P.\text{positive}, P.\text{negative}$ はパターン $P$ が抽出したインスタンス事例について、それぞれ手元のインスタンスに合致した数、合致しなかった数を表します。

更にパターンが抽出したインスタンスの確信度をパターンの確信度を元に算出します。インスタンス $T$ を生成したすべてのパターン $P = {P_i}$の確信度と、パターン $P_i$ が生成したインスタンス事例の持つ実際の文脈 $C_i$ を用いて、インスタンス $T$ の確信度は以下のように表されます。

\text{Conf}(T) = 1 - \prod^{|P|}_{i=0}(1 - (\text{Conf}(P_i) \cdot \text{Match}(C_i, P_i)))

インスタンスの抽出のフェーズではこの確信度が一定のしきい値を上回っているかどうかを基準にして、新しくインスタンスが決定されます。

また、一つ前のイテレーションにおけるパターンの確信度が計算されていれば、現在のイテレーションにおけるパターンの確信度との重み付けによって、インスタンス抽出で用いるパターンの確信度の計算がなされます。この値は重みを $W_\text{updt}$として

\text{Conf}(P) = \text{Conf}_\text{new} (P) \cdot W_\text{updt} + \text{Conf}_\text{old} (P) \cdot (1 - W_\text{updt})

で計算されます。

Semi-Supervised Bootstrapping of Relationship Extractors with Distributional Semantics (2015)

• David S. Batista, et al. Semi-Supervised Bootstrapping of Relationship Extractors with Distributional Semantics 2015

Snowballの文脈ベクトルの表現をカウント中心のbow表現からword2vecベースの分散表現を足し上げたものに置き換えた論文です。

特質すべきなのは、著者がGihtubで論文の実装を公開しており。あわせてSnowballの実装も公開しています。

著者論文と合わせてSnowballの詳細な手続きを追うのに大変有用な情報源となっています。

github.com

github.com

広告

この記事はMNTSQ勤務中に書かれた。

MNTSQは情報抽出に関心のあるエンジニアを募集しています。

www.wantedly.com

参考文献

• 情報抽出・固有表現抽出のための基礎知識
• 情報抽出入門 〜非構造化データを構造化させる技術〜
• Espresso 型ブートストラッピング法における意味ドリフトのグラフ理論に基づく分析 2010
• Extracting Patterns and Relations from the World Wide Web 1999
• Snowball: Extracting Relations from Large Plain-Text Collections 2000
• Semi-Supervised Bootstrapping of Relationship Extractors with Distributional Semantics 2015
• GitHub - roomylee/awesome-relation-extraction: 📖 A curated list of awesome resources dedicated to Relation Extraction, one of the most important tasks in Natural Language Processing (NLP).

---

1. 統計学における、標本を重複を許して抽出する手法とは異なります。↩

正規表現を用いる際のパフォーマンスチェックリスト

Python で正規表現を書いて分析や機械学習のモデル構築、予測に活用する際には、正規表現実行時のパフォーマンスが足かせとなる場合があります。

正規表現の処理に用いられる実行時間がどのくらいになるかはテキストデータの分量や機械学習モデルの精度検証の実行回数に応じて変わってきます。

一つのテキストデータに対する正規表現の実行時間を少なくすることで、タスクによっては全体として大幅な処理時間の短縮が見込まれます。そのことによって精度検証を素早く回したり、テキスト処理実行時の前処理の実行時間を削減する等の効果が得られます。精度検証の間の実行待ち時間やバッチ・キューによる予測時の時間が減り、最終的には精度向上の機会の向上やサービスのユーザ体験の向上に繋がるというわけです。

本記事では Python を用いた場合の正規表現のパフォーマンス改善候補についてリストアップし、具体的な対応方法について見ていきます。

Table of contents

環境情報

本記事でのコードの実行環境は以下の通りです。

• MBP 2019 (macOS Catalina)
• Python 3.6.7
• pandas 1.0.1 (一部 0.25.3 )
• fb-re2 1.0.6

実行環境の用意は下記の記事を参考にDockerで作成しました。

qiita.com

環境構築にあたって利用したDockerイメージはこちらです。

• windj007/jupyter-keras-tools

正規表現をコンパイルする

Python で正規表現を扱う際には定番の re モジュールですが、大きめの正規表現を繰り返し用いることが想定される場合には予め compile メソッドを用いてコンパイル*1しておくと、トータルとしての実行時間を削減できます。

In

import re
import timeit

target_text = 'kou123otsu'
digit_pattern = r'\d+'
count = 100

def direct_use():
    for _ in range(count):
        re.search(digit_pattern, target_text)

def compile_once():
    regex = re.compile(digit_pattern)

    for _ in range(count):
        regex.search(target_text)

def compile_everytime():
    for _ in range(count):
        regex = re.compile(digit_pattern)
        regex.search(target_text)


for func in [direct_use, compile_once, compile_everytime]:
    print(func)
    %timeit func()

Out

> <function direct_use at 0x7ff9904998c8>
> 119 µs ± 1.05 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> <function compile_once at 0x7ff96991c598>
> 47.9 µs ± 470 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> <function compile_everytime at 0x7ff96991c510>
> 111 µs ± 935 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

関数	実行時間	実行時間% (per direct_use)
direct_use	119µs	100%
compile_once	47.9µs	40%
compile_everytime	111µs	93%

尚、トータルとしてとあえて断ったのは、この例での通常の利用ケースを想定した関数 direct_use の中でも二回目の実行以降はコンパイルされた正規表現パターンが実行されているためです。

というのも、re ライブラリ側の実装として、通常のマッチング関数に渡されたパターンはキャッシュが効くようになっています。

docs.python.org

しかし、下記記事によれば、キャッシュが効いていたとしても、キャッシュに対する検索時間がかかるという旨の考察がなされています。

teratail.com

やはり大量に同じパターンを用いる場合はコンパイルした正規表現を渡しておいたほうが実行時間的には無難といえます。

複数マッチや文字クラスでまとめられそうな表現は一つにまとめる

検索対象が複数の文字列に及ぶ場合、正規表現として文字クラス等を用いて一つにまとめたほうが処理が速いです。

In

import re
import timeit

target_text = '契約期間中に解約しようとするときは通知しなければならない'
count = 100

def sub_redundantly():
    target_words = ['契約', '解約']
    for _ in range(count):
        result = target_text
        for word in target_words:
            result = re.sub(word, 'XXX', result)

def sub_all():
    word_pattern = '[契解]約'
    for _ in range(count):
        result = target_text
        result = re.sub(word_pattern, 'XXX', result)
        
for func in [sub_redundantly, sub_all]:
    print(func)
    %timeit func()

Out

> <function sub_redundantly at 0x7f3b61056ea0>
> 256 µs ± 1.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> <function sub_all at 0x7f3b618a4bf8>
> 200 µs ± 2.96 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

関数	実行時間	実行時間% (per sub_redundantly)
sub_redundantly	256µs	100%
sub_all	200µs	78%

for 文の中で複数の似たような単語を同時に変換しているような処理はパフォーマンス改善対象の候補になるでしょう。

キャプチャを伴わないグループ化 (?:) を用いる

正規表現を用いて () 内に囲ったパターンにマッチした一部の文字列を抽出することはキャプチャと言われますが、キャプチャは正規表現内で明示的に避けることができます。キャプチャを避けることで正規表現の実行のパフォーマンスにも若干の違いが出てきます。

In

import re
import timeit

target_text = 'https://subdomain.company.co.jp/{}/index.html'.format('/'.join([chr(i) for i in range(97, 97+26)]))
print(target_text)
subdomain_pattern_1 = r'$https?://([a-z]+)\.[a-z]+(\.co\.jp|\.ac\.jp)/([a-z]+/)*(index|title).html'
subdomain_pattern_2 = r'$https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html'
count = 100

def capture_all():
    regex = re.compile(subdomain_pattern_1)
    for _ in range(count):
        regex.search(target_text)

def capture_only_subdomain():
    regex = re.compile(subdomain_pattern_2)
    for _ in range(count):
        regex.search(target_text)    


for func in [capture_all, capture_only_subdomain]:
    print(func)
    %timeit func()

Out

> https://subdomain.company.co.jp/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/index.html
> <function capture_all at 0x7fb28fe87d08>
> 62.5 µs ± 680 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> <function capture_only_subdomain at 0x7fb28fe87d90>
> 60.6 µs ± 836 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

関数	実行時間	実行時間% (per capture_all)
capture_all	62.5µs	100%
capture_only_subdomain	60.6µs	97%

これはターゲット文字列が極端な例ですが、キャプチャが行われないことで実行時間に若干の違いが出ています。(しかしそこまでの差ではない）

pandas の str アクセサについて

pandas の str アクセサは文字列操作について汎用的な操作を提供しますが、バージョンによっては pd.Series の replace を用いた方が速いです。

In

import pandas as pd
import timeit

target_text = '契約期間中に解約しようとするときは通知しなければならない'
count = 100
df = pd.DataFrame({'text': [target_text] * count}, dtype=str)
word_pattern = '[契解]約'

def replace_by_accessor():
    df["text1"] = df["text"].str.replace(word_pattern, 'XXX', regex=True)

def replace_by_ordinal():
    df["text2"] = df["text"].replace(word_pattern, 'XXX', regex=True)
    
for func in [replace_by_accessor, replace_by_ordinal]:
    print(func)
    %timeit func()

Out

pandas == 0.25.3
> <function replace_by_accessor at 0x7fc054daff28>
> 523 µs ± 11.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> <function replace_by_ordinal at 0x7fc054dafea0>
> 483 µs ± 15.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

pandas == 1.0.1
> <function replace_by_accessor at 0x7f8864198ae8>
> 562 µs ± 40 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> <function replace_by_ordinal at 0x7f8864198a60>
> 584 µs ± 18.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

関数	pandas ver	実行時間	実行時間% (per replace_by_accessor, pandas==0.25.3)
replace_by_accessor	0.25.3	523µs	100%
replace_by_ordinal	0.25.3	483µs	92%
replace_by_accessor	1.0.1 (latest)	562µs	107%
replace_by_ordinal	1.0.1 (latest)	584µs	112%

この記事を書くまでの筆者環境は 0.25.3 であったため、このTipsを載せましたが、1.0.1 では実行時間が逆転して str アクセサのほうが短くなっています。

また、どちらの方法もバージョン更新後の方が実行時間がかかるようになっているため、latest な pandas はパフォーマンスという点については必ずしも改善されているわけでは無いと言えます。

re2

Google が開発した re2 エンジンは C++ で書かれた DFA型(deterministic finite automaton) の高速な正規表現エンジンです。

Python の re パッケージで用いられているものとは正規表現エンジンのタイプが異なり、実行できない文法も存在します。（後方参照や再帰機能）

この記事では re2 エンジンについて特に深追いはしません。以下の記事や書籍には更に詳しい解説がされています。

naoyat.hatenablog.jp

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

実際のソースコードでも実行時間が短縮されているかどうか確認してみます。

In

import re
import re2
import timeit

target_text1 = 'kou123otsu'
digit_pattern = r'\d+'

target_text2 = 'https://subdomain.company.co.jp/{}/index.html'.format('/'.join([chr(i) for i in range(97, 97+26)]))
subdomain_pattern = r'$https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html'

counts = [100, 1000, 10000]


def search_by_re(count, target, pat):
    regex = re.compile(pat)
    for _ in range(count):
        regex.search(target)


def search_by_re2(count, target, pat):
    regex2 = re2.compile(pat)
    for _ in range(count):
        regex2.search(target)


for func in [search_by_re, search_by_re2]:
    print(func)
    
    print('target : ' + target_text1)
    print('pattern : ' + digit_pattern)
    
    for count in counts:        
        %timeit func(count, target_text1, digit_pattern)
        
    print('target : ' + target_text2)
    print('pattern : ' + subdomain_pattern)
    
    for count in counts: 
        %timeit func(count, target_text2, subdomain_pattern)

Out

> <function search_by_re at 0x7f8863ad80d0>
> target : kou123otsu
> pattern : \d+
> 42.6 µs ± 313 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 424 µs ± 2.86 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 4.52 ms ± 36.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
> target : https://subdomain.company.co.jp/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/index.html
> pattern : $https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html
> 59.9 µs ± 643 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 595 µs ± 2.13 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 6.02 ms ± 65.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
> <function search_by_re2 at 0x7f8863ad8620>
> target : kou123otsu
> pattern : \d+
> 137 µs ± 821 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 1.21 ms ± 22.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 11.8 ms ± 87.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
> target : https://subdomain.company.co.jp/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/index.html
> pattern : $https?://([a-z]+)\.[a-z]+(?:\.co\.jp|\.ac\.jp)/(?:[a-z]+/)*/(?:index|title).html
> 89.2 µs ± 1.55 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
> 521 µs ± 7.27 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
> 4.81 ms ± 67.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

関数	pattern	実行回数	実行時間	実行時間% (per search_by_re)
search_by_re	digit	100	42.6µs	100%
search_by_re2	digit	100	137µs	322%
search_by_re	digit	1000	424µs	100%
search_by_re2	digit	1000	1.21ms	285%
search_by_re	digit	10000	4.52ms	100%
search_by_re2	digit	10000	11.8ms	261%
search_by_re	subdomain	100	59.9µs	100%
search_by_re2	subdomain	100	89.2µs	149%
search_by_re	subdomain	1000	595µs	100%
search_by_re2	subdomain	1000	521μs	88%
search_by_re	subdomain	10000	6.02ms	100%
search_by_re2	subdomain	10000	4.81ms	80%

先程紹介の書籍内にも解説があり、深く原因を追求することは本記事では避けますが、必ずしも re2 のほうが優れているというわけではなく、どういった正規表現を用いるか、実行回数のスケールに応じて結果が異なっています。

例えば、\d+ の正規表現については re を用いた処理のほうがパフォーマンスが高いのに対し、サブドメインを取得する２つめの正規表現については、実行回数のスケールが増えるに従い、re2 を用いた処理のほうが徐々にパフォーマンスが高くなっています。

パフォーマンスの改善によるサービス全体への改善成果と、正規表現のパターンに応じてライブラリの使い分けをするコストを踏まえてこの類の改善はしていきたいところです。

広告

この記事はMNTSQ勤務中に書かれた。

MNTSQは正規表現のパフォーマンス向上に関心のあるエンジニアを募集しています。

www.wantedly.com

参考リンク

• Regex Performance in Python - Towards Data Science
• Five invaluable techniques to improve regex performance
• 正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

*1:この記事ではコンパイルという単語の意味について深追いすることはしません。コンパイルの内部の仕組みは正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)に詳しいです。