4. 文字列プログラミング

本日の話題

プログラミング言語の文字列処理

文字列処理アルゴリズム

文字列とは

文字を並べたももの

e.g. "abcdefg"

プログラミング言語で最もよく使われるデータ構造のひとつ

プログラミング言語と文字列処理

文字列処理とパタンマッチング

最近のプログラミング言語では普通

文字列は標準的なデータ構造

"abc" + "def" ?

C言語ではこういう表現はできない

Perl, Ruby, Python, JavaScript, などモダンな言語では普通

SNOBOL

StriNg Oriented symBOlic Language

文字列処理に特化したプログラミング言語

文字列処理関数いろいろ

パターンマッチング

連想配列

最近の傾向

文字列は最近のプログラミング言語の基本要素

Perl, Ruby, Python, JavaScript, ...

Unix文化で常識化

awk, grep, sed, ...

文字列は数値などと同じ扱い

a = b + 20

s = "abc" + "def"

最近の言語のテキスト処理 (Ruby, Java, JS, etc.)

連結

"abc" + "def"

"abc" . "def"

パタンマッチング

正規表現利用

/pat*ern/

部分文字列切り出し

文字置換

連想配列

a['abc']

文字列処理の例

s =~ /From:\s.*masui/

s = "<div>" + p + "</div>"

「+」には注意が必要

'123' + 1 => '1231' ? 124 ?

JavaScriptの文字列連結

以下を実行

code:string.js

a = "abc";

b = a + "def";

alert(b);

Demo: Rubyでの文字列連結

文字列操作関数の比較

高林氏による比較表

http://gyazo.com/f912c0076f784b0ea142f71665749156.png

Cでの文字列プログラミング

文字列 == 配列

メモリ操作関数

strcat(), strcmp(), etc.

大変めんどくさい

オーバーフローの危険がある

脆弱性がよく攻撃された

e.g. Heartbleed(2014), Morris Worm(1988)

Cの文字列のデータ構造

a = "abc"

メモリの中身: a b c 0

b = "def"

メモリの中身: a b c 0 d e f 0

a = a + b

メモリの中身: a b c 0 d e f 0 a b c d e f 0

「abc」はこれ以降利用されない

これを繰り返すとメモリが足りなくなる (「メモリリーク」)

「ガベージコレクション」が必要

配列と連想配列

配列

a[10]

a[0], a[1], ... がメモリ上に並ぶ

連想配列

a['abc']

データ構造は自明ではない

「ハッシュ」と呼ばれることがあるが不適切

ハッシュを利用した連想配列

http://gyazo.com/5bf88c89ce08c15c51830a2bd5a8ea76.png

Trie(トライ)による連想配列の実装

http://gyazo.com/2605770240f7d6cd5ba63fb4d74632ac.png

マクロプログラミング

第2回を参照

Cプリプロセッサ、m4コマンド

文字列検索アルゴリズムとデータ構造

配列解析アルゴリズム特論 by 渋谷@東大

遺伝子解析に利用

各種マッチングアルゴリズム解説

高速文字列解析の世界

http://www.amazon.co.jp/dp/4000069748 https://gyazo.com/a9a5851fab882bb99fa2395061735b0f.png

Burrows-Wheeler変換など

各種のアルゴリズム

パタンマッチングアルゴリズム

完全マッチ

正規表現

曖昧マッチ

類似計算

完全パタンマッチ

文字列T[1..n]中のパタンP[1..m]の出現位置を計算

単純に比較していくと遅い

各種の高速アルゴリズム

Knuth-Morris-Pratt (KMP)法

Boyer-Moore法

Shifterアルゴリズム

超単純アルゴリズム

T[1..m]と P[1..m] を比較

T: aaaaaaaaaaaaaaaaab

P: aaaaaab

T[2..m] とP[1..m]を比較

T: aaaaaaaaaaaaaaaaab

P: aaaaaab

...

T[n-m+1..n]とP[1..m]を比較

最悪の場合約 $ n \times m 回の文字比較が必要

Knuth-Morris-Pratt法

P[7] (= b)で不一致が検出されたとき

前のテキストはaaaaaaであることが既知

P[6] (= a)の比較をやり直せばよい

不一致が検出されたときに比較をやりなおすべきPの文字の位置をあらかじめ「失敗関数」として計算

無駄な比較を繰り返さないようにする

http://gyazo.com/1d7b988f5207f5d70182f576cd28e525.png

Knuth-Morris-Pratt法の例

P = abcaba の場合

http://gyazo.com/981d1b79dceedfa85cf5995ea44be3b4.png

5 → 1 の遷移

5の状態でテキストの最後がabcaであることが既知

→2の状態まで戻れる

5から6に遷移できない場合

次の文字はbでない

→1の状態まで戻れる

Boyer-Moore法

最速といわれるテキスト検索アルゴリズム

文字比較回数が文字列長より少なくてすむ

KMP法ではテキストの文字をすべて比較しなければならない

パタンの右端からマッチを調べる

1回目の文字比較でT[m] = c であることがわかる

cはPに含まれていないので2回目の比較はT[m+1]の先から調べればよい

http://gyazo.com/c0ef58ec05df6c96c8591907363c7b2c.png

Boyer-Moore法 (Cont'd)

右からk文字だけ一致したときにその次にどこから比較を再開すればよいかをあらかじめパタンから計算

2個の表を用意

d1 -- 右端で不一致が検出されたときの、移動数[不一致文字]の表

d2 -- 右からk文字目で不一致が検出されたときの、移動数[不一致位置]の表

先の例の場合、d1['a'] = 1, d2['c'] = d1['d'] = ... = 8である。

シフタアルゴリズム

長さ$ mの文字列検索のマッチ状態を$ mビットで表現

$ k文字マッチを$ k番目のビットで表現

e.g. 0110000 = 2文字、3文字マッチ

次の文字がcであるとき、この状態変数を1ビット右にシフトし、S[c]とのandを計算することにより新しい状態を計算

S[c]はあらかじめ計算しておく値で、パタン文字==cの位置だけ1になっている。

e.g. パタンabac → T['a'] = 1010, T['b'] = 0100

シフタアルゴリズム実行例

code: shifter.txt

t = 'abacde', p = 'abac'

s'a' = '1010', s'b' = '0100', s'c' = '0001'

v = '11111111111'

v = v & s[t0] → '10100000000'

v 右シフト → '01010000000'

v = v & s[t1] → '0100000000'

v 右シフト → '0010000000'

v = v & s[t2] → '0010000000'

v 右シフト → '0001000000'

v = v & s[t3] → '0001000000'

v 右シフト → '000010000000' マッチ!

シフタアルゴリズム

条件によってはBMより高速

曖昧検索ユティリティagrepで使用

Ricardo Baeza-Yates

https://gyazo.com/39e3e5be4880072ecbd4043c2012e9ab

テキスト検索アルゴリズムの研究者

Yahoo! LabsのVPをやってた

Modern Information Retrieval

https://www.amazon.co.jp/dp/0321416910 https://gyazo.com/dc972a0ac2249ec5de93c61e467a6075

Udi manber

https://gyazo.com/cf22699b1637e1ec84a8441a23c4db9c

agrep の開発者

テキスト検索アルゴリズム研究者

元 Yahoo! のチーフサイエンティスト

元 Amazonのチーフアルゴリズムオフィサー

元GoogleのエンジニアリングVP

正規表現

文字列のパタンを指定して検索

曖昧な検索ができる

e.g. 「〇山×郎さん」を探す

Unixでポピュラーになった

正規表現パタン

選言

「aまたはb」

文字集合

「英数字」

繰り返し

「aが3個以上並んだもの」

正規表現の例

abc

(abc|def)

[abc]

ab*c

Demo: grep

正規表現の例

(時計|時間|時刻)を([0-9]*)時に(セットする|設定する|あわせる)

ファイルを((きっちり(きっちり)?)?)消す

詳説正規表現

https://gyazo.com/e7954093bc6f257d3976be3aa6d9fb82

正規表現技術入門

アルゴリズムについて書かれている

https://www.amazon.co.jp/dp/B07JHRL2NS https://gyazo.com/a7cf80318f7d193f583a6f9dbeb36562

言語の生成文法

言語の文を生成する規則

終端記号(e.g. 「山」)と非終端記号(e.g. 名詞)

名詞 ← 「山」

名詞句 ← 形容詞名詞

正規文法

正規表現を表現する文法

チョムスキー階層の最も単純なもの

A ← aB という形式のみ (A/B: 非終端記号, a: 終端記号)

Norm Chomsky

https://gyazo.com/378d3fe7e44ba4df3a182acc36d73c4a.png

エイヴラム・ノーム・チョムスキー（Avram Noam Chomsky、1928年12月7日 - ）は、アメリカ合衆国の哲学者、言語哲学者、言語学者、認知科学者、論理学者。マサチューセッツ工科大学の言語学および言語哲学の研究所教授 (Institute Professor) 兼名誉教授。

正規表現の実現

同等の状態遷移機械に変換可能

e.g. a(b|cd) に対応する文法と状態遷移機械

A ← aS

B ← bA

C ← cA

B ← dC

http://gyazo.com/ef47894d05a71d085fb31cdd9527910e.png

正規表現のパタンマッチ

Aho-Corasick法

grep方式

egrep方式

Aho-Corasick法

(文字列1|文字列2|...) の形のパタンの認識

KMP法の拡張

失敗関数を使用(KMP法よりも複雑)

fgrepコマンドで使用

例: ac|baa|bacd|ba|bbの認識

http://gyazo.com/7926b6c03cc66c5f883d4aa2a4a14da7.png

grep方式

UNIXのgrepコマンドで使用

*、?などのパタンを受け持つ関数を再帰的に呼ぶことによりパタンマッチを行なう

abc|defのようなパタンを認識できない

「ソフトウェア作法」に解説有り

表現は美しいが速度は遅い

egrep方式

UNIXのegrepコマンドで使用

任意の正規表現パタンを使用可能

アルゴリズム

正規表現からNFA(非決定性状態遷移機械)を作成

NFAからDFA(決定性状態遷移機械)を作成

DFAを表現する遷移テーブルを作成

パタン作成の手間はかかるがパタンマッチ実行は高速

非決定性状態遷移機械の例

パタン (SUB)*SECTION

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

変換計算

http://gyazo.com/d9e5779fe46637b3fedf7783e0e2d1d3.png

変換された決定性状態遷移機械

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

変換された決定性状態遷移機械

http://gyazo.com/c74f45af19228955d3a50cb796d6781b.png

(もとの非決定性状態遷移機械)

http://gyazo.com/2df5627603e51e8f04ed465eda1e9f4b.png

正規表現でできないこと

数を数えられない

状態を保持できない

「左括弧と右括弧の数が同じ」ようなパタンを検出できない

曖昧マッチができない

曖昧パタンマッチ

ちょっとした違いを許容する

文字欠落、余分な文字、異なる文字

正規表現では表現しにくい

e.g. abacから1文字欠落 => /bac|aac|abc|aba/

曖昧検索アルゴリズム

agrep

シフタアルゴリズムの拡張

「ピテカン検索」

曖昧検索辞書

「pitekan」から「Pithecanthropus」を検索

ピテカン検索

https://gyazo.com/70769e2cc5e8d228630e707dbdcbc81d http://www.pitecan.com/tmp/DragZoom/eiwa3.html

曖昧検索の状態遷移図の例

http://gyazo.com/33d3ba9323939d1f9426a25d24184078.png

動作例

http://gyazo.com/33a87ab418c6e283073219e7d021d387.png

Demo: Scrapboxの検索

正規文法を使って文章を生成する

/(sub)*section/にマッチする文字列

⇒ "section", "subsection", "subsubsection", ...

文字列は自動的に生成可能

RegExpの展開

例

(時計|時間|時刻)を(0|1|2|3|4|5|6|7|8|9|10|11|12)時に(セットする|設定する|あわせる)

時計を0時にセットする

時計を0時に設定する

時計を0時にあわせる

時計を1時にセットする

時計を1時に設定する

時計を1時にあわせる

時計を2時にセットする

時計を2時に設定する

...

re_expand.rb

code:expand.rb

require 're_expand'

'(月|火|水|木|金)曜(1|2|3|4|5|6)限)'.expand { |s,a|

puts s

}

実行結果

code:result.txt

月曜1限

月曜2限

月曜3限

月曜4限

月曜5限

月曜6限

火曜1限

火曜2限

火曜3限

火曜4限

...

SFCHelp

SFC生のためのヘルプシステム

https://scrapbox.io/SFCHelp/ https://gyazo.com/96443ec139c8fa1a90df21bca63f5273

SFCHelpの記述例

https://scrapbox.io/SFCHelp/%E7%B6%BA%E9%BA%97%E3%81%AA%E3%83%88%E3%82%A4%E3%83%AC https://gyazo.com/bbeb462a3bcfd0f4d06db7af2a5179fb

HelpFeel

展開された文字列と曖昧検索する

https://gyazo.com/54ce6ce8a5ada4af1d5e453e6fc5e4d9 https://helpfeel.notainc.com/SFCHelp/

Helpfeel導入例

Helpfeel解説動画

https://www.youtube.com/watch?v=lzEvFLV9WS4

https://www.youtube.com/watch?v=1axZR2Rgitk

https://www.youtube.com/watch?v=dJ84fBycEmc

文字列操作でゲーム

Rewrite Rule (GRR)

code:GRR.rb

s = "-------=>------------=>-------"

while true do

s.gsub!(/=>\-/,'-=>')

s.gsub!(/=>$/,'<=')

s.gsub!(/\-<=/,'<=-')

s.gsub!(/^<=/,'=>')

s.gsub!(/=><=/,'<==>')

puts s

end

Result

code:result.txt

---=>-----<=------------------

----=>---<=-------------------

-----=>-<=--------------------

------<==>--------------------

-----<=--=>-------------------

----<=----=>------------------

---<=------=>-----------------

--<=--------=>----------------

-<=----------=>---------------

=>------------=>--------------

-=>------------=>-------------

--=>------------=>------------

---=>------------=>-----------

----=>------------=>----------

-----=>------------=>---------

------=>------------=>--------

-------=>------------=>-------

--------=>------------=>------

---------=>------------=>-----

----------=>------------=>----

-----------=>------------=>---

------------=>------------=>--

-------------=>------------=>-

--------------=>-----------<=-

---------------=>---------<=--

----------------=>-------<=---

-----------------=>-----<=----

------------------=>---<=-----

-------------------=>-<=------

--------------------<==>------

-------------------<=--=>-----

------------------<=----=>----

-----------------<=------=>---

----------------<=--------=>--

箱入り娘

http://gyazo.com/3a7c99ef1f715532976f7e9489408483.png

箱入り娘を解く

https://www.youtube.com/watch?v=azOaRBhernY

状態を文字列で表現

http://gyazo.com/ab3c088f1f7e81f8ab772a706168db43.png

s = "3223*4224*3553*4664*6016"

文字列置換規則

code:hakoiri.rb

s = "3223*4224*3553*4664*6016"

pats = [

/220(..)221/, "022\\1122",

/022(..)122/, "220\\1221",

/01(...)22(...)22/, "22\\122\\201",

/22(...)22(...)01/, "01\\122\\222",

/30(...)41/, "03\\114",

/03(...)14/, "30\\141",

/0(....)3(....)4/, "3\\14\\20",

/1(....)3(....)4/, "3\\14\\21",

/3(....)4(....)0/, "0\\13\\24",

/3(....)4(....)1/, "1\\13\\24",

[/55(01)/, "\\155"],

[/(01)55/, "55\\1"],

/01(...)55/, "55\\101",

/55(...)01/, "01\\155",

]

strstate = {}

statestr = {}

states = 0

statestrstates = s

strstates = states

states += 1

prev = {}

i = 0

while i < states do

s = statestri

pats.each { |pair|

pat = pair0

replace = pair1

if pat.match(s) then

ss = s.dup

ss.sub!(pat,replace)

ss.sub!(/(01)(.*)(01)/, "0\\21")

if strstatess.nil? then

prevstates = i

statestrstates = ss

strstatess = states

if /22.$/.match(ss) then

STDERR.puts states

while prevstates do

output(statestrstates)

states = prevstates

end

output(statestrstates)

exit

end

states += 1

STDERR.puts states if states % 1000 == 0

end

}

i += 1

end

実行結果

code:result.txt

======

父父父父

親親親親

小小番頭

娘娘小

======

父父父父

親親親親

小小番頭

娘娘　小

======

父父父父

親親親親

小小番頭

娘娘小　

娘娘　小

======

父父父父

親親親親

小小番頭

娘娘　　

娘娘小小

======