Comments
Description
Transcript
PCクラスタ上での文字列編集距離計算の並列化
PCクラスタ上での文字列編集距離計算の並列化
氏名：竹林幸那
学籍番号：2260070106-5
指導教員：山崎勝弘
提出日：平成23 年2 月17 日
立命館大学
理工学部
電子情報デザイン学科
1
内容梗概
文字列編集距離はスペルチェッカーや、近似文字列照合、また、バイオインフォマティ
クス分野で活用されており、DNA 配列同士の類似性を判断するために応用されていて、この
ような計算量が大きい問題に対して、並列処理は特に有効である。近年のＰＣクラスタな
どの普及により、並列処理はより身近なものとなっている。
本研究では文字列の編集距離をレーベンシュタイン距離のアルゴリズムを用いて逐次プ
ログラムを C 言語、並列プログラムを OpenMP で作成し、編集距離を計り、その実行時間の
計測を行った。また、並列プログラムを Nycto クラスタ上に実装し、スレッドの台数を１
～８台に変更して実験を行った。その結果、20000 文字以上の文字列ではスレッドの台数を
増やすごとに速度向上する結果になった。それぞれスレッド数が８台で実行したときは、
スレッド台数が１台のときに比べて、20000 文字では 3.9 倍、30000 文字では 4.2 倍、40000
文字では 5.2 倍、50000 文字では 10.9 倍の速度向上が得られることがわかった。また、実
行する文字列が長いほど速度向上が得られたが、文字列を長くしすぎるとセグメンテーシ
ョンエラーが発生してしまい、実行することができなかった。今後の課題としては１0000
文字を 2 回に分けるなどのプログラムの改善が必要だと思われる。
2
目次
1. はじめに..............................................................................................................................1
2. 文字列編集距離計算のアルゴリズム ..................................................................................3
2.1 レーベンシュタイン距離とは .......................................................................................3
2.2 レーベンシュタイン距離のアルゴリズム .....................................................................3
3. C 言語による実験 ................................................................................................................8
3.1 実験内容 ......................................................................................................................8
3.2 実験結果 ......................................................................................................................8
3.3 考察 .............................................................................................................................9
4. 文字列編集距離計算の並列化手法 .................................................................................. 10
4.1 PC クラスタ ............................................................................................................. 10
4.2 並列プログラミング ................................................................................................. 10
4.3 並列化手法 ................................................................................................................ 11
5. PC クラスタ上での並列化の実験..................................................................................... 13
5.1 実験環境 ................................................................................................................... 17
5.2 実験結果 ................................................................................................................... 18
5.3 考察 .......................................................................................................................... 19
6. おわりに........................................................................................................................... 20
謝辞 ....................................................................................................................................... 17
参考文献 ............................................................................................................................... 18
付録 1 C プログラム
付録 2
c-levenshtein.c.............................................................................22
OpenMP プロラム
openmp-levenshtein.c...............................................................26
3
図目次
図 2.1
レーベンシュタイン距離の擬似コード.....................................................................4
図 2.2
操作回数を求める表..................................................................................................5
図 2.3
文字列が同一のときのセル値の求め方.....................................................................5
図 2.4
文字列が異なるとき 左上セルの値＋１.................................................................6
図 2.5
文字列が異なるとき 左セルの値＋１.....................................................................6
図 2.6
文字列が異なるとき 上セルの値＋１.....................................................................6
図 2.7 w と i の比較...............................................................................................................7
図 3.1
逐次プログラムの処理時間.......................................................................................8
図 4.1
並列化方法..............................................................................................................11
図 4.2
ウェーブフロントによる並列化..............................................................................12
図 5.1
Nycto の構成............................................................................................................13
図 5.2
並列化の速度向上比................................................................................................14
表目次
表 2.1
weight と write の編集距離.......................................................................................7
表 3.1 逐次プログラムでの編集距離と処理時間..................................................................8
表 5.1 Nycto クラスタ上での処理時間(sec) .......................................................................14
4
1.はじめに
文字列編集距離はスペルチェッカーや、近似文字列照合などで利用されている。近似文
字列照合とは、検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検
索のことである。また、バイオインフォマティクス分野で活用されており、DNA 配列同士の
類似性を判断するために応用されている。これは DNA が挿入・欠失・置換の 3 様式によっ
て変化していくことの反映である。異なる生物種が持つ同様の遺伝子を同定したり、また
それらの距離を測ったりすることで種が分岐してから経過した時間を推定するなどを実現
している。[1]
このような計算量が大きい問題に対して、並列処理は特に有効である。近年のＰＣクラ
スタなどの普及により、並列処理はより身近なものとなっている。PC クラスタとは複数台
の PC を組み合わせ、
それぞれの PC が協調動作するように設計されたシステム全体を言う。
ＰＣクラスタは、既存のＰＣを組み合わせてネットワークを構成するだけで作ることがで
きるため、一般の並列計算機に比べて導入が容易である。
また、近年では複数のプロセッサコアを搭載した汎用コンピュータが普及している。近
年のプロセッサは周波数の向上による高速化から、プロセッサコアを増やす高速化に方向
転換している。プロセッサの性能向上だけに頼る高速化は限界に近づきつつあり、マルチ
コアプロセッサなどによる並列化を採用する方向へ転換しつつある。つまり、ハードウェ
アとソフトウェアが協調し、処理を並列化して高速化を図るのである。
本研究ではレーベンシュタイン距離のアルゴリズムを用いて、文字列の編集距離と実行
時間を計る。レーベンシュタイン距離とは、情報理論において、二つの文字列がどの程度
異なっているかを示す数値である。具体的には、文字の挿入や削除、置換によって、一つ
の文字列を別の文字列に変形するのに必要な手順の最小回数として与えられる。本研究で
は、まず C 言語を用いた逐次プログラムで実験を行い、文字列編集距離と実行時間を計る。
実験では write と wrote を 10 文字、100 文字、1000 文字、5000 文字、10000 文字、20000
文字と連続させたテストデータを使用する。次に、OpenMP を用いて並列プログラムを作成
し、実験を行う。並列化手法としては、このプログラムの各セルの値は、左上のセル値、
上のセル値、左のセル値を参照しているため、ウェーブフロントで並列化を行う。この
OpenMP で並列化したプログラムを Nycto クラスタ上に実装し、スレッドの台数を１～８台
に変更する。この実験では、文字数を 10 文字、1000 文字、10000 文字、20000 文字、30000
文字、40000 文字、50000 文字と変更して文字列編集距離を計り、その実行時間の計測を行
った。
第２章では文字列編集距離のアルゴリズム、レーベンシュタイン距離について述べる。
第 3 章では逐次プログラムである C 言語で文字列の編集距離計算を行ったときの実験内容、
5
結果、考察について述べる。第 4 章では、PC クラスタや並列プログラミングについ述べた
後、本研究で行った並列化手法について述べる。第 5 章では、PC クラスタを用いた並列処
理に必要な実験環境について述べた後、並列化させたアルゴリズムの並列化を行い、並列
化したアルゴリズムの PC クラスタ上での実験結果と考察について述べる。全体のまとめに
ついては第６章に記述する。
6
2.文字列編集距離計算のアルゴリズム
2.1 レーベンシュタイン距離とは
２つの文字列の近さを計るために片方の文字列に次の操作を繰り返し適用して、もう一
方の文字列を得るための操作回数の最小値を、その２つの文字列のレーベンシュタイン距
離あるいは、編集距離という。[2]
使用可能な操作は以下の 3 種類である。
1.
削除
:
1 つの文字を取り除く
2.
挿入
:
1 つの文字を新たに付け加える
3.
置換
:
1 つの文字を別の文字で置き換える
例えば、「weight」と「write」の編集距離を考えるとき、次のように操作を繰り返し適用
すると、この 2 つの編集距離が 4 以下であることが分かる。
weight
weighte(挿入：e)
wrighte(置換：e → r)
writhe(削除：g)
write(削除：h)
また、3 回以下の操作の適用では「weight」を「write」にすることができないので、
「weight」
と「write」の編集距離は 4 となる。挿入、削除、置換は文字列のどの位置で行ってもよい。
2.2 レーベンシュタイン距離のアルゴリズム
レーベンシュタイン距離を計算するためには、一般的に動的計画法によるアルゴリズムが
用いられている。長さ n と長さ m の文字列間の距離を求めるには、(n + 1)×(m + 1) の
二次元行列が使われ、計算時間は O(mn)と非常に効率がよい。
このアルゴリズムの要諦は、以下の 2 点から帰納的に求めることができるという点である
1 文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、1 文
字削った文字列との距離から 1 文字加えた文字列との距離を求めることができる
長さ 0 の文字列と長さ x の文字列の距離は x である
図 2.1 に、文字数 lenStr1 の文字列 str1 と、文字数 lenStr2 の 文字列 str2 間のレー
7
ベンシュタイン距離を求める擬似コードを示す。
int LevenshteinDistance ( char str1[ 1..lenStr1 ], char str2[ 1..lenStr2 ] )
// lenStr1 + 1 行 lenStr2 + 1 列のテーブル d を用意する
declare int d[ 0..lenStr1, 0..lenStr2 ]
// str1 と str2 を数え上げる変数 i1 と i2 を用意する
declare int i1, i2, cost
for i1 from 0 to lenStr1
d[ i1, 0 ] := i1
for i2 from 0 to lenStr2
d[ 0, i2 ] := i2
for i1 from 1 to lenStr1
for i2 from 1 to lenStr2
if str1[ i1 ] = str2[ i2 ] then cost := 0
else cost := 1
d[ i1, i2 ] = minimum(
d[ i1 - 1, i2
d[ i1
] + 1,
// 文字の挿入
, i2 - 1 ] + 1,
// 文字の削除
d[ i1 - 1, i2 - 1 ] + cost
)
return d[ lenStr1, lenStr2 ]
図 2.1
レーベンシュタイン距離の擬似コード
8
// 文字の置換
長さ M の文字列１と長さ N の文字列２の編集距離は以下の手順で求めることができる。
① 図 2.2 のような操作回数を求める表を作る。
図 2.2 操作回数を求める表
② 最左列，最上行のセルは 1～N，1～M の値と仮定する。
③ テーブルの左上から下に値を求める。
④ 上，左上，左のセル値と，当該の行と列の文字列を使い，以下の方法で各セルの値
を計算する。
A) 文字列が同一ならば左上セルの値
B) 異なるならば左上セルの値+1
C)
左セルの値+1
D)
上セルの値+1
⑤
(B)-(D)の最小値をセルの値に設定する
⑥
右下端のセル値が最終的な編集距離となる
例えば、write と weight の２つの文字列の編集距離の求めるためには、まず、文字列の
先頭の文字の W と W を比較する。この場合は文字列が同一なので、図 2.3 ようにセルの値
は左上の値をそのまま使用する。0 がセルの値となる。
1
0
1
W
W
0
図 2.3 文字列が同一のときのセル値の求め方
9
編集距離はテーブルの左上から下に求めるため、次は w と r を比較する。この場合は、
文字列が異なるため、図 2.4～図 2.6 のように左上のセルの値＋１、左セルの値＋１、上セ
ルの値＋１を求める。
1
0
W
1
W
0
2
r
2
図 2.4 文字列が異なるとき 左上セルの値＋１
1
0
W
1
W
0
2
r
３
図 2.5 文字列が異なるとき 左セルの値＋１
1
0
W
1
W
0
2
r
１
図 2.6 文字列が異なるとき 上セルの値＋１
10
この３つの中では、図 2.6 の上セルの値＋１したときが最小値なので、この値をセル値に
設定する。
次に w と i を比較する。この場合も、上セルの値＋１したときが最小値になるので図 2.7
のようにセルの値は２になる。
1
0
W
1
W
0
2
r
１
3
i
２
図 2.7
w と i の比較
このように下方向に比較をして、１列目の値が求まる。次に２列目の e とｗの比較を行
い、２列目すべての値を求める。この操作を６列目まで繰り返していき右下のセル値を求
める。このセルの値が最終的な編集距離となる。よって、weight と write の編集距離は４
となる。
表 2.1 weight と write の編集距離
1
2
3
4
5
6
0
W
e
i
g
h
t
1
W
0
１
２
３
４
５
2
r
１
１
２
３
４
５
3
i
２
２
１
２
３
４
4
t
３
３
２
２
３
３
5
e
４
４
３
３
３
４
11
3.C 言語による実験
3.1 実験内容
実験では Intel Core™2 Duo CPU E6850 3.00GHz、メモリ 4GB の PC を使用した。
write と wrote を 10 文字、50 文字、250 文字、500 文字、2500 文字、5000 文字、10000
文字と連続させたテストデータを使って編集距離と、結果が出力されるまでの処理時間を
計ることにする。
例えば、10 文字の場合は writewrite と wrotewrote のテストデータで編集距離と、処理
時間を計る。この場合の編集距離は２、結果が出力されるまでの時間は 0.015 秒となった。
3.2 実験結果
表 3.1 逐次プログラムでの編集距離と処理時間
10 文字
100 文字
500 文字
1000 文字
5000 文字 10000 文字 20000 文字
編集距離
2
20
100
200
1000
2000
4000
時間(sec)
0.015
0.015
0.015
0.015
0.34
0.937
6.281
7
6
5
4
3
時間(sec)
2
1
0
図 3.1
逐次プログラムの処理時間
12
3.3 考察
実験結果より、10 文字、100 文字、500 文字、1000 文字の時の実行時間には変化がない
ことがわかる。これは、文字列が短いため、編集距離を計算するためにかかる時間に差が
あらわれないと考えられる。
5000 文字、10000 文字、20000 文字は、文字数が増加すると編集距離計算に時間も増加す
ることがわかる。編集距離が 5000 文字以上になると実行時間に差が現れると考える。
13
4.文字列編集距離計算の並列化手法
4.1
PC クラスタ
PC クラスタとは複数台のPCを組み合わせ、それぞれのPCが協調動作するように設計され
たシステム全体を言う。協調動作を行わせるためには、専用のソフトウェアが必要となり、
クラスタ内のPC がネットワークで接続されている必要がある。またPC クラスタを動作さ
せて計算を行わせるためには並列プログラムが必要となる。これらの要件を備えることに
よって、PC クラスタはPC クラスタを構成する個々のPC を意識することなく、まるで1 台
のPC のように扱うことができる。
PC クラスタが利用されるのは主にプログラムの高速化である。この用途に利用されるク
ラスタは高性能クラスタHPC（Highperformanceclusters）とも呼ばれる。HPC はクラスタ
の各ノードに処理を分散させることにより高速化を実現している。HPC の並列プログラミ
ング実行環境として、SCore とBeowulf が有名である。
SCore 型クラスタとは、 Score Cluster System Software を用いて構成されたクラスタ
である。SCore Cluster Systerm Software は、通信ライブラリであるPMv2、グローバルオ
ペレーティングシステムであるSCore-D、ソフトウェアDSM(Distributed Shared Memory)シ
ステムであるSCASH などで構成されているが、一番の特徴は、SCASH によって物理的に分
散したメモリを共有メモリとして扱うことができることである。これにより、単一プロセ
ッサのPC を繋げたPC クラスタでも、共有メモリ環境で並列プログラミングを行うことが
できる。
Beowulfとは、HPC クラスタを構成する方式の総称のことであり、Beowulf方式で構成さ
れたクラスタをBeowulf 型クラスタという。各ノードにはLinuxなどのフリーのUNIX 系OS
がインストールされており、互いに高速なネットワークで接続されている。並列プログラ
ミング環境としてPVM やMPI などのライブラリを用いることが多い。クラスタシステムソ
フトウェアなどの特別なソフトウェアを使わずに構成できることが大きな特徴である。
4.2 並列プログラミング
第 3 章の逐次プログラムを OpenMP で並列化する。
OpenMP とは、並列コンピューティング環境を利用するために用いられる標準化された基
盤である。OpenMP は主に共有メモリ型並列計算機で用いられる。
MPI では明示的にメッセージの交換をプログラム中に記述しなければならないが、OpenMP
は OpenMP が使用できない環境では無視されるディレクティブを挿入することによって並
14
列化を行う。このため並列環境と非並列環境でほぼ同一のソースコードを使用できるとい
う利点がある。
MPI との比較では、OpenMP は異なるスレッドが同一のデータを同じアドレスで参照で
きるのに対して、MPI では明示的にメッセージ交換を行わなければならない。そのため SMP
環境においては大きなデータの移動を行なわずにすむので高い効率が期待できる。ただし
並列化の効率はコンパイラに依存するのでチューニングによる性能改善が MPI ほど高くな
らないという問題がある。また、OpenMP は MPI に比べてメモリアクセスのローカリティ
が低くなる傾向があるので、頻繁なメモリアクセスがあるプログラムでは、MPI の方が高
速な場合が多い。現在 FORTRAN と C/C++について標準化が行われている。
4.3 並列化手法
このプログラムの各セルの値はデータ依存しているため、左上、上、左のセルの値が定
まっていないと計算することが出来ない。そこで、以下のように並列化を行う。
まず、最初文字列を比較し、セルの値を確定する。図 4.1 のように最初のセルの値が確
定すると、右セルの値と下セルの値を同時に求めることができる。
図 4.1
並列化方法
次に、図 4.2 のように左上、上、左のセルの値が定まっているセルの値を求める。この操
作で３つのセルの値を同時に求めることができる。
15
図 4.2
ウェーブフロントによる並列化
この操作を繰り返し行うことで、逐次プログラムより高速に文字列編集距離を求めるこ
とができる。
16
5.PC クラスタ上での並列化の実験
5.1 実験環境
本研究では、Nycto クラスタを使用する。Nycto クラスタの構成を図 5.1 に示す。 Nycto
の計算ノードは、Nycto00 と Nycto01 の計 2 台で、それぞれが Gigabit Ethernet Switch を
介して、ホストサーバである Bronto と繋がっている。Nycto00 と Nycto01 にはそれぞれ、
Quad Xeon が２台と８GB のメモリが搭載されており、全部で１６プロセッサ、１６GB メモ
リである。Nycto への操作は Bronto を介して行う。Nycto 上には、OS である CentOS4.4 の
他に、PC クラスタ用の高性能並列プログラミング環境である SCore（Ver.6.0.2）が動作し
ている。 Nycto を使用するためにはまず Score を起動させなければならない。
図 5.1
Nycto の構成
17
5.2 実験結果
この実験も第３章と同じように、write と wrote を 10 文字、1000 文字、10000 文字、20000
文字、30000 文字、40000 文字、50000 文字と連続させたテストデータを使って編集距離と、
結果が出力されるまでの処理時間を計測する。
表 5.1 Nycto クラスタ上での処理時間
5 文字
単位：秒
１０００文字
10000 文字
20000 文字
30000 文字
40000 文字
50000 文字
1台
0.000131
0.008631
0.814674
3.528972
11.73662
32.56188
90.34023
２台
0.000213
0.029389
0.931257
3.134749
6.772511
10.79532
18.2781
４台
0.000173
0.04493
0.971879
2.366654
4.81004
7.579532
11.38584
８台
0.000392
0.057042
1.005256
2.1805
4.211364
6.277142
8.315002
12
速度向上比
10
8
20000文字
6
30000文字
4
40000文字
50000文字
2
0
1
2
4
8
図 5.2 並列化の速度向上比
18
スレッド数（台）
5.3 考察
並列化を行い、Nycto クラスタ上でスレッドの台数を１台から８台まで増やした結果、実
行台数を増やすと速度が向上した。しかし、３章の C 言語での実験と同様に、5 文字、1000
文字、10000 文字の場合はスレッドの台数を増やすと速度が遅くなった。これは、短い文
字列なのでスレッドに振り分ける作業に時間がかかってしまうためだと考える。
また、50000 文字以上ではセグメンテーションエラーが発生してしまい、実行すること
ができなかった。これは、文字列が長すぎるからだと考えられる。１0000 文字を 2 回に分
けるなどのプログラムの改善が必要かもしれない。
19
6.おわりに
本研究では、文字列編集距離を計算するために、逐次プログラムと並列プログラムを作
成し、実行時間を計測した。並列プログラムは、Score 型クラスタである Nycto 上でスレッ
ド台数を１~8 台に変えて実行した。
逐次プログラムも並列プログラムも、文字列が短いときには実行時間が変化しなかった
り、速度が遅くなったりする結果となった。
しかし、並列プログラムでは 20000 文字以上ではスレッドの台数を増やすごとに速度が
向上した。それぞれスレッド数が８台で実行したときは、スレッド台数が１台のときに比
べて、20000 文字では 3.9 倍、30000 文字では 4.2 倍、40000 文字では 5.2 倍、50000 文字
では 10.9 倍の速度向上が得られることがわかった。
20
謝辞
本研究の機会を与えてくださり、貴重な助言、ご指導をいただきました山崎勝弘教授に深
く感謝いたします。 また、貴重な助言を下さった高性能計算研究室の皆様に心より深く感
謝いたします。
21
参考文献
[1]レーベンシュタイン距離
<http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3
%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2>
[2] 北山洋幸 :“ OpenMP 入門―マルチコアCPU 時代の並列プログラミング ”、秀和
システム、2009.
[3] Cell Challenge 2009
<http://www.hpcc.jp/sacsis/2009/cell >
[4] CORMEN, THOMAS H、LEISERSON, CHARLES ERIC、RIVEST, RONALD L, 浅野哲夫 訳, 梅
尾 博司 訳,和田幸一 訳,岩野和生 訳,山下雅史 訳 : アルゴリズムの設計と解析手法、近
代科学社、1995.
[5] OpenMP入門
<http://olab.is.s.u-tokyo.ac.jp/~reiji/openmp.html>
[6]南扶友子: 文字列照合のOpenMPによる並列化, 立命館大学
理工学部電子情報デザイン学科卒業論文, 2010
[7]黒川 耕平: PC クラスタ上での OpenMP 並列プログラミング（Ⅱ）, 立命館大学
理工学部情報学科卒業論文, 2003
22
付録 1 C プログラム
c-levenshtein.c
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <malloc.h>
#include "second.c"
#define print_kokoko
¥
for(j=0; j<=n; j++){¥
for(i=0; i<=m; i++){¥
printf("%3d ", kokoko[j][i]);¥
}¥
puts("");¥
}¥
#define MAX
20000
int levenshteinDistance(char *A,char *B) {
int i,j;
int min,r;
int m,n;
//int *tmp;
int kj = 0;
int ki = 0;
int kr = 0;
int hako1 = 0;
int hako2 = 0;
int *kokoko;
int kekka;
m = strlen(A);
n = strlen(B);
23
kokoko = (int *) malloc (sizeof(int*) * MAX * MAX);
for (i = 1; i <= m; i++){
kokoko[i] = A[i-1];
}
for (i = 1; i <= n; i++){
kokoko[i*MAX] = B[i-1];
}
for (i = 1; i <= n; i++){
for (j = 1; j <= m; j++){
if(kokoko[i*MAX] == kokoko[j]){
kokoko[i*MAX+j] = kokoko[(i-1)*MAX+(j-1)];
else{
kj = kokoko[(i-1)*MAX+(j-1)] + 1;
ki = kokoko[i*MAX+(j-1)] + 1;
kr = kokoko[(i-1)*MAX+j] + 1;
if(kj >= ki){
hako1 = ki;
}
else if(kj < ki){
hako1 = kj;
}
if(hako1 >= kr){
hako2 = kr;
}
24
else if(hako1 < kr){
hako2 = hako1;
}
kokoko[i*MAX+j] = hako2;
}
}
}
kekka=kokoko[n*MAX+m];
free(kokoko);
return kekka;
}
int main()
{
int dist;
double start,end;
FILE *fp;
char mojiA[MAX], mojiB[MAX];
start = seconds();
//ファイルを開く
fp = fopen("test20000.c", "r");
if (fp == NULL){
printf("error!!¥n");
return(0);
}
//ファイルから文字を読み込む
fscanf(fp, "%s %s¥n", mojiA, mojiB);
25
dist = levenshteinDistance(mojiA, mojiB);
printf("Distance = %d¥n", dist);
//ファイルを閉じる
fclose(fp);
end = seconds();
printf("jikan=%lfsec¥n", end-start);
return(0);
}
26
付録 2 OpenMP プログラム
openmp-levenshtein.c
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <malloc.h>
#include "second.c"
#ifdef _OPENMP
#include<omp.h>
#endif
#define print_kokoko
¥
for(j=0; j<=m; j++){¥
for(i=0; i<=n; i++){¥
printf("%3d ", kokoko[i*MAX+j]);¥
}¥
puts("");¥
}¥
#define MAX
20000
int *kokoko;
int compare(char *A,char *B,int i,int j){
int kj = 0;
int ki = 0;
int kr = 0;
int hako1 = 0;
int hako2 = 0;
if(kokoko[i*MAX] == kokoko[j]){
return(kokoko[(i-1)*MAX+(j-1)]);
}
27
else{
kj = kokoko[(i-1)*MAX+(j-1)] + 1;
ki = kokoko[i*MAX+(j-1)] + 1;
kr = kokoko[(i-1)*MAX+j] + 1;
if(kj >= ki){
hako1 = ki;
}
else if(kj < ki){
hako1 = kj;
}
if(hako1 >= kr){
hako2 = kr;
}
else if(hako1 < kr){
hako2 = hako1;
}
return(hako2);
}
}
int levenshteinDistance(char *A,char *B) {
int i,j;
int ii,jj;
int min,r;
int m,n;
int kekka;
m = strlen(A);
n = strlen(B);
28
kokoko = (int *) malloc (sizeof(int*) * MAX * MAX);
for (i = 1; i <= m; i++){
kokoko[i] = A[i-1];
}
for (i = 1; i <= n; i++){
kokoko[i*MAX] = B[i-1];
}
for(i=1; i<=m; i++){
#pragma omp parallel for private(ii, jj, j)
for(j=1; j<=i; j++){
ii=i+1-j;
jj=j;
//printf(" %d, %d¥n", ii, jj);
kokoko[ii*MAX+jj] = compare(A, B, ii, jj);
}
}
for(i=(n-1); i>=0; i--){
#pragma omp parallel for private(ii, jj, j)
for(j=1; j<=i; j++){
ii=n+1-j;
jj=j+(n-i);
//printf(" %d, %d¥n", ii, jj);
kokoko[ii*MAX+jj] = compare(A, B, ii, jj);
}
}
kekka = kokoko[n*MAX+m];
free(kokoko);
return kekka;
}
29
int main()
{
int dist;
double start,end;
FILE *fp;
char mojiA[MAX], mojiB[MAX];
#ifdef _OPENMP
//OpenMP を使ったコード
#pragma omp parallel num_threads(8)
{
if (omp_get_thread_num() == 0){
printf("Parallel
Running!
omp_get_num_threads());
}
}
#endif
//ファイルを開く
fp = fopen("test20000.c", "r");
if (fp == NULL){
return(0);
}
//ファイルから文字を読み込む
fscanf(fp, "%s %s¥n", mojiA, mojiB);
//printf("Distance¥n");
start = seconds();
dist = levenshteinDistance(mojiA, mojiB);
end = seconds();
printf("Distance = %d¥n", dist);
//ファイルを閉じる
fclose(fp);
30
Running
on
%d
thread.¥n",
printf("jikan=%lfsec¥n", end-start);
return(0);
}
31