7 文字列照合

文字列照合のアルゴリズムとして，単純照合法およびKMP法を実装する．

ソースコードは，次のURLからダウンロードできる．

• dsa-code-string.zip

7.1 単純照合法

readFile.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

/**
 * ファイルを読み込みむ．
 * @param path 読み込むファイルのパス
 * @param str 読み込んだ文字列を格納する配列へのポインタ
 * @return 読み込んだファイルのサイズ（バイト数）．
 */
int readFile(char* path, char* str) {
  FILE* fp = NULL;

  fp = fopen(path, "r");
  if ((fp = fopen(path, "r")) == NULL) {
    perror("Cannot not open file");
    exit(1);
  }

  int len = 0;
  while (!feof(fp))
    str[len++] = (char)fgetc(fp);
  fclose(fp);
  str[--len] = '\0';  // 末尾のEOFを削除
  return len;
}

cmp.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

extern bool isVerbose;
extern int Ncmp;

/**
 * 文字比較関数．比較回数をカウントする．
 * @param a 比較文字
 * @param b 比較文字
 * @return a と b が等しければ true, 等しくなければ false.
 */
bool cmp(char a, char b) {
  if (isVerbose)
    fprintf(stderr, "cmp(%c, %c)\n", a, b);
  Ncmp++;
  if (a == b)
    return true;
  else
    return false;
}

mainNaive.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define PAT_MAX 256     // パターンの最大の長さ
#define TEXT_MAX 1024 * 1024 * 10 // テキストの最大の長さ（10 MB）

bool isVerbose = false;     // 比較回数表示スイッチ
unsigned int Ncmp = 0;      // 比較回数のカウンタ

int readFile(char*, char*);
bool cmp(char, char);

/**
 * 単純照合法による文字列照合．
 * @param text テキスト
 * @param pat 検索パターン
 * @return 照合に成功した位置．失敗した場合は -1．
 */
int naive(char* text, unsigned int textlen, char* pat, unsigned int patlen) {
    // コードを完成させる．
}


/**
 * メイン関数
 * @param argc
 * @param argv
 * @return 終了ステータス：正常終了 0 / それ以外 1
 */
int main(int argc, char** argv) {
  char pat[PAT_MAX];    // 検索パターン
  char* text = (char *)malloc(TEXT_MAX * sizeof(char));
  int patlen = 0;
  int textlen = 0;

  // 引数処理・ファイル読み込み
  if (argc < 3 || 4 < argc) {
    fprintf(stderr, "Usage: ./main [-v] <text file> <pattern file>\n");
    return 1;
  }
  int i = 1;
  if (strcmp(argv[i], "-v") == 0) {
    isVerbose = true;
    i++;
  }
  textlen = readFile(argv[i++], text);
  patlen = readFile(argv[i], pat);

  // pat 末尾の改行コードを削除
  while (pat[patlen - 1] == '\r' || pat[patlen - 1] == '\n')
    pat[--patlen] = '\0';

  // 文字列照合・結果表示
  if (isVerbose) {
    printf("text size: %d\n", textlen);
    printf("pattern size: %d\n", patlen);
  }
  printf("Pattern found at %d.\n", naive(text, textlen, pat, patlen));
  if (isVerbose)
    printf("# of comparison(s): %d.\n", Ncmp);

  free(text);

  return 0;
}

Makefile

#CC = gcc
#CFLAGS = -g

all: mainNaive mainKMP

mainNaive: cmp.o readFile.o mainNaive.o 

mainKMP: cmp.o readFile.o mainKMP.o 

clean:
    rm -f *.o mainNaive mainKMP

コンパイルと実行

$ make mainNaive
cc    -c -o mainNaive.o mainNaive.c
cc    -c -o cmp.o cmp.c
cc    -c -o readFile.o readFile.c
cc   mainNaive.o cmp.o readFile.o   -o mainNaive
$ echo This is a pen. > text
$ echo pen > pat
$ ./mainNaive text pat
Pattern found at 10.

パターンが存在しない場合は -1 を表示する．

$ echo ix > pat
$ ./mainNaive text pat
Pattern found at -1.

また，"-v" オプションとともに実行すると，比較の詳細と比較回数を表示する．

$ ./mainNaive -v text pat
text size: 15
pattern size: 2
cmp(i, T)
cmp(i, h)
（略）
Pattern found at -1.
# of comparisons: 17.

プログラムの説明

• C言語では，文字列は char 型の配列として扱い，文字列の終端はナル文字 '\0' で識別される．
• ファイルから文字列を読み出す場合，改行コードも文字として扱われることに注意すること．改行コードは OS によって異なるが，macOS や Linux では '\n' が用いられる．今回のサンプルコードでは，検索パターンの末尾の改行コードは削除するようになっている．
• 文字の比較回数を調査するために，cmp()関数を用意している．各文字の比較の際にこの関数を呼び出すと，比較回数を格納するカウンターが加算される．また，"-v" オプションを指定することで，比較回数の表示を簡単に行うことができる．

基本課題1

1. 単純照合法に基づいて，上記のコードにおけるnaive()を作成してプログラムを完成させなさい．
2. 作成したプログラムを簡単な動作例を用いて説明し，それが正しく動作することを示しなさい．

7.2 KMP法

mainKMP.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define PAT_MAX 256     // パターンの最大の長さ
#define TEXT_MAX 1024 * 1024 * 10 // テキストの最大の長さ（10 MB）

bool isVerbose = false;     // 比較回数表示スイッチ
unsigned int Ncmp = 0;      // 比較回数のカウンタ

int readFile(char*, char*);
bool cmp(char, char);

/**
 * next配列の計算
 * @param pat パターン配列
 * @param next next配列
 * @return なし
 */
void compnext(char* pat, unsigned int* next) {
  // 関数を完成させる．
  return;
}


/**
 * KMP法による文字列照合．
 * @param text テキスト
 * @param pat 検索パターン
 * @return 照合に成功した位置．失敗した場合は -1．
 */
int kmp(char* text, unsigned int textlen, char* pat, unsigned int patlen) {
  unsigned int next[PAT_MAX];   // NEXT配列
  // 関数を完成させる
}


/**
 * メイン関数
 * @param argc
 * @param argv
 * @return 終了ステータス：正常終了 0 / それ以外 1
 */
int main(int argc, char** argv) {
    // mainNaive.c と同様なので省略．
}

基本課題2

1. compnext関数を完成させなさい．
2. 作成したcompnext関数が正しく動，KMP法によって文字列照合を行うプログラムを作成しなさい．
3. KMP法に基づいて，上記のコードにおけるkmp()を作成してプログラムを完成させなさい．
4. 作成したプログラムを簡単な動作例を用いて説明し，それが正しく動作することを示しなさい．

7.3 発展課題：文字列照合アルゴリズムの比較

発展課題1

長さnの文字列に対して，長さmのパターンを照合することを考える．

• 異なる長さの文字列に対して，単純照合法とKMP法の比較回数を実際に調査し，どちらが高速か検討しなさい．
• 調査した比較回数のデータは散布図などを使って可視化すると良い．散布図の作成には，gnuplot や Python（Matplotlib）などが利用できる．
• サイズの大きなテキストとしては，Linuxに付属している辞書ファイルなどを利用すると良い．
  • www.coins.tsukuba.ac.jp: /usr/share/dict/words

発展課題2

• 単純照合法で最悪となる文字列およびパターンはどのようなものか．実例を挙げるとともに，計算量をオーダで示しなさい．
• さらに単純照合法で最悪となる文字列およびパターンに対してKMP法における比較回数を調査し，どちらが高速かを検討しなさい．

7.4 提出ファイルの構成

• ディレクトリ class7 を作成して，その中に上記ファイルを配置すること．
• class7 を ZIP で圧縮した class7.zip ファイルを manaba に提出すること．

[class7.zip）の構造]
class7/
  +- report7.pdf
  +- mainKMP.c*
  +- mainNaive.c
  +- cmp.c      // 配布ファイルと同一
  +- readFile.c // 配布ファイルと同一
  +- Makefile   // 配布ファイルと同一

7.5 提出締切

2025年1月27日（月）13:30