文字列の解析 その3: 正規表現の歴史

第1回では文字列から特定パターンの部分を切り出すことがなぜ必要になるのか、そして第2回ではパターンが複雑になるとそれを実装するコードがとても複雑になるということと、その複雑なコードを人間が書くのではなくコンピュータに作らせる「正規表現」について学びました。

ここではその正規表現がどのように生まれてきたのか、軽く歴史を振り返ってみましょう。[1]

(注:書きかけです)

マッカロピッツのニューラルネット

1943年、Warren McCulloch と Walter Pittsの2人が神経細胞(ニューロン)の振る舞いをモデル化して、複数の神経がネットワークとしてどういう振る舞いをしうるかについての研究を発表しました。[2] 後のニューラルネットワークにつながる研究です。[3]

この論文の中で彼らは、複雑なニューロンの接続関係を表現するために、独自の記法を発明しました。

(脚注[1] 今回の話は「詳説正規表現」P.83〜P.88の内容をベースにしています)

(脚注[2] McCulloch, Warren S., & Pitts, Walter H. (1943), "A Logical Calculus of the Ideas Immanent in Nervous Activity", Bulletin of Mathematical Biophysics (Chicago: University of Chicago Press) 5: 115-133.「神経細胞は興奮しているかどうかで1/0の二値の値を出力する」「興奮性の入力と抑制性の入力がある」「興奮性の入力がしきい値を超えると興奮する」などの今でもよく使われるニューロンのモデルは彼らが考えたものです。そのため、この種のニューロンをMcCulloch-Pitts型ニューロンと呼びます。

(脚注[3]: なお現在だと「バックプロパゲーション付きのパーセプトロン」を指して「ニューラルネット」という言葉を使う人も多いですが、パーセプトロンが生まれたのが1962年、バックプロパゲーションが生まれたのが1986年、とだいぶ後の話なので混同しないように気をつける必要があるでしょう。)

クリーネによる統一

ニューラルネットの研究だけではありませんでした。この時期は「言語をきっちり定義できる形で研究しよう」という形式言語学や、「計算機をモデル化しよう」というオートマトン理論の研究も盛んな時期でした。そしておのおのの分野で、似たようなものを表現するために色々な記法が発明されました。

Stephen Kleeneはこれを整理し、正規集合(regular set)、正規言語(regular language)、正規表現(regular expression)などの用語を発明しました。つまり「正規表現」という言葉の直接の発明者は、Stephen Kleeneです。

「0回以上のくりかえし」を意味するアスタリスク(*)を「クリーネ閉包」や「クリーネスター」と呼ぶのは彼に由来しています。

(TODO:要検討 Jeffrey E. F.Friedlの説明に引きずられてストーリーの出だしをニューラルネットにしてしまったけども、形式言語学とオートマトンの理論の方にもっと紙面をさいたほうがよいのではないか？)

(TODO: http://www.sciencedirect.com/science/bookseries/0049237X/101 のRobert L. Constable "The Role of Finite Automata in the Development of Modern Computing Theory* Original Research Article" Pages 61-83 を読んで、Kleeneが何を統一しようとしていたのかの記述を見つける)

(Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automata". In Shannon, Claude E.; McCarthy, John. Automata Studies. Princeton University Press. pp. 3–42)

文字列検索への応用

  • 1968 Ken Thompson: "Regular Expression Search Algorithm"
  • egrep Alfred Aho (いつ生まれた？)

(脚注 Ken Thompsonの業績としては、1969年にC言語の前身であるB言語を作ったことなどが挙げられる。2013年現在GoogleでGo言語の開発に携わっている)
(脚注 Alfred Ahoの業績としては、1977年にAWKという正規表現を扱える言語が生まれている。この言語の名前はAlfred Aho, Peter Weinberger Brian Kernighanの頭文字を取って命名された。K&RのK。)
(The complexity of regular(-like) expressions http://dl.acm.org/citation.cfm?id=1881467)

標準化(これは削ってもいいかも)

  • 1993 POSIX(Portable Operating System Interface)による正規表現の標準化(ISO/IEC 9945-2:1993)

Perlの発展とPCREの登場

(脚注: 正規表現の発展を引っ張ってきたPerlだが、Parl 6 Rulesで互換性の大部分を捨てて新しいエンジンに移行しており、今後他の言語へどう影響するかが興味深い)
(TODO: 「初の」に関して意見が割れる可能性がある。「汎用」の定義依存。)

Rubyと鬼車

(書きかけです)