Rustでワイルドカードを実装してみよう

• 

  ワイルドカードの関数を作ってみよう

ワイルドカードとは

正規表現を知らない人でも、ワイルドカードなら分かるという方は多くいます。ファイルやデータベースの検索をする際、ワイルドカードであれば、あまり考える事なく気軽に検索に利用できます。今回は、Rustでワイルドカードを実装してみましょう。

そもそも、「ワイルドカード(Wildcard)」とは、検索を行う時、コンピュータで特定の文字や文字列の代わりに使える記号のことです。「*」や「?」などの特殊記号を利用して、特別なパターンを表現できます。一般的なファイル検索で使えるワイルドカードには「*」と「?」があります。

例えば、「*」は任意の0文字以上の文字列を表します。「*.txt」でファイル検索したとき、拡張子「.txt」の全てのファイル「abc.txt」や「書類.txt」、「202408.txt」などのファイルを検索できなす。

「*」は任意の0文字以上の文字列を表し「?」は任意の1文字を表します。「test-?.xlsx」と指定すれば「test-1.xlsx」「test-2.xlsx」「test-a.xlsx」などのファイルを検索できます。

ワイルドカードをどのように実装したら良いか？

それでは、具体的にワイルドカードをどのように実装したら良いのか考えてみましょう。

まず、ワイルドカード関係なく、ただの文字列パターンが、文字列1と一致するかどうかを確認する場合には、次の図のように先頭の文字から1文字ずつそれぞれが一致するかを末尾まで確認することになります。

• 

  パターンと文字列を1文字ずつ確認

ワイルドカードを実装する場合でも、基本的に同じです。ワイルドカードの「?」は任意の1文字のみを確認するので、「?」の部分にはどんな文字でも合致することにして確認すれば良いのです。

• 

  ワイルドカードの場合も同じ - パターンと文字列を1文字ずつ確認

次に、ワイルドカード「*」を考えてみましょう。「*」は0文字以上の任意の文字を表します。そのため、次の図のように、文字列2とパターンが合致するかは、「*」のワイルドカードの部分を1文字ずつ飛ばして確認して、ワイルドカードの後から末尾が合致するかを確かめることになります。

• 

  ワイルドカードの場合も同じ - パターンと文字列を1文字ずつ確認

つまり、「ab*.txt」というパターンに対して、文字列2「abcde.txt」がマッチするかを確認するには、パターンの3文字目の「*」を見つけた時点で、「cde.txt」がパターンの残りの部分「.txt」と合致するのかを検証します。そのために、「*」が0文字の任意文字だった場合、1文字の任意文字だった場合、2文字の任意文字だった場合…と検証していきます。

Rustで実装してみよう

Rustで実装する場合、少しコツが必要です。まず、日本語などの多バイト文字列(Unicode)に対応するために文字列(String)を1文字ずつに分割して、Vec<char>に変換します。その上で、文字列がパターンに合致するのか1文字ずつ確認します。

いきなりワイルドカードの「?」と「*」を実装してしまうと混乱してしまいそうです。そこで、まずは、「?」だけを実装してみましょう。

最初にRustのプロジェクトを作成しましょう。ターミナル(WindowsならPowerShell、macOSならターミナル.app)を起動して、下記のコマンドを実行しましょう。

mkdir wildcard_simple
cd wildcard_simple
cargo init

すると、プロジェクトのひな形が作成されます。そこで、src/main.rsを開いて、次のように編集してみましょう。(こちらにもアップしています - https://gist.github.com/kujirahand/e97ad3fd090ebd96619be18aaae30e11)

fn main() {
    // 「ab?.txt」が「abc.txt」にマッチするか --- (*1)
    println!("{}", is_match("ab?.txt", "abc.txt")); // true
}

// ワイルドカードのパターン「?」を使った文字列マッチング --- (*2)
fn is_match(pattern: &str, target: &str) -> bool {
    // &strをVec<char>に変換してis_match_sliceを呼び出す
    let pattern: Vec<char> = pattern.chars().collect();
    let target: Vec<char> = target.chars().collect();
    is_match_slice(&pattern, &target)
}

// ワイルドカードのパターン「?」を使った文字列マッチング --- (*3)
fn is_match_slice(pattern: &[char], target: &[char]) -> bool {
    let mut ip = 0;
    let mut it = 0;
    // 1文字ずつ順に比較していく --- (*4)
    while ip < pattern.len() && it < target.len() {
        if pattern[ip] == '?' { // 任意の1文字にマッチ --- (*5)
            ip += 1;
            it += 1;
        } else if pattern[ip] == target[it] { // 文字が一致 --- (*6)
            ip += 1;
            it += 1;
        } else {
            return false; // マッチしない
        }
    }
    // パターンも対象も末尾まで到達した場合にtrueを返す --- (*7)
    ip == pattern.len() && it == target.len()
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        // いろいろなパターンを試してみる --- (*8)
        assert_eq!(is_match("ab?.txt", "abc.txt"), true);
        assert_eq!(is_match("a??.txt", "abc.txt"), true);
        assert_eq!(is_match("?", "abc.txt"), false);
        assert_eq!(is_match("a?.txt", "abc.txt"), false);
        assert_eq!(is_match("????.txt", "test.txt"), true);
    }
}

プログラムを実行するには、ターミナルで下記のコマンドを実行しましょう。

cargo run

プログラムが正しく動けば、trueと表示されます。

• 

  正常に実行できた時、何も表示しない

また、プログラムの末尾にテストを記述しました。下記のコマンドを実行することで、テストだけを実行して動作を確認できます。

cargo test

正しくテストが実行されると、「test result: ok. 1 passed; 0 failed; ...」と表示されます。もし、テストに書いたassert_eq!が失敗すると、どのテストで失敗したかを表示します。

• 

  テストを実行したところ

プログラムを確認してみましょう。(＊1)では、関数is_matchを記述しています。(＊2)では、&strをVec<char>に変換して関数is_match_sliceを呼び出します。これにより、日本語のような多バイト文字列に変換します。

(＊3)ではパターンマッチを行う関数is_match_sliceを記述します。(＊4)では基本的に1文字ずつ引数patternとtargetを付き合わせていきます。(＊5)ではワイルドカードの「?」を確認します。これは、任意の1文字にマッチするものなので、patternとtargetの確認位置のカーソルipとitを1ずつ進めるだけです。(＊6)では、文字が一致するかどうかを確認して、カーソルを進めます。そして、(＊7)では、カーソルが共に末尾に達しているかどうかを確認します。文字列の長さが異なる場合、関数の戻り値はfalseとなります。

(＊8)ではテストを記述します。#[cfg(test)] mod tests { ... } のように書く事で、テストであることを明示できて、コマンド「cargo test」でテストを実行できるようになります。

ワイルドカードの「*」にも対応しよう

続いて、ワイルドカードのパターン「*」にも対応するように、プログラムを改良してみまししょう。次のように修正しましょう。(こちらにもアップロードしています - https://gist.github.com/kujirahand/843c34e789af18551c01f22f6cdfab90)

fn main() {
    // 「ab?.txt」が「abc.txt」にマッチするか --- (*1)
    println!("{}", is_match("ab?.txt", "abc.txt")); // true
}

// ワイルドカードのパターン「?」を使った文字列マッチング --- (*2)
fn is_match(pattern: &str, target: &str) -> bool {
    // &strをVec<char>に変換してis_match_sliceを呼び出す
    let pattern: Vec<char> = pattern.chars().collect();
    let target: Vec<char> = target.chars().collect();
    is_match_slice(&pattern, &target)
}

// ワイルドカードのパターンを使った文字列マッチング --- (*3)
fn is_match_slice(pattern: &[char], target: &[char]) -> bool {
    let mut ip = 0;
    let mut it = 0;
    // 1文字ずつ順に比較していく --- (*4)
    while ip < pattern.len() && it < target.len() {
        if pattern[ip] == '*' { // 0文字以上の任意文字にマッチ --- (*5)
            ip += 1; // ワイルドカードをスキップ
            // ワイルドカードの次の文字が一致するまで繰り返す
            for i in it..target.len() {
                // 新たなスライスを作って再帰的にマッチングを行う
                let sub_pattern = &pattern[ip..];
                let sub_target = &target[i..];
                if is_match_slice(sub_pattern, sub_target) {
                    return true;
                }
            }
            continue;
        }
        if pattern[ip] == '?' { // 任意の1文字にマッチ --- (*6)
            ip += 1;
            it += 1;
            continue;
        }
        if pattern[ip] == target[it] { // 文字が一致 --- (*7)
            ip += 1;
            it += 1;
            continue;
        }
        return false; // マッチしない
    }
    // パターンも対象も末尾まで到達した場合にtrueを返す --- (*8)
    ip == pattern.len() && it == target.len()
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test() {
        // いろいろなパターンを試してみる --- (*9)
        assert_eq!(is_match("ab?.txt", "abc.txt"), true);
        assert_eq!(is_match("a*.txt", "abc.txt"), true);
        assert_eq!(is_match("*.txt", "abc.txt"), true);
        assert_eq!(is_match("a?g.txt", "abcdefg.txt"), false);
        assert_eq!(is_match("a*g.txt", "abcdefg.txt"), true);
        assert_eq!(is_match("a*b*g.txt", "abcdefg.txt"), true);
        assert_eq!(is_match("*efg.txt", "abcdefg.txt"), true);
    }
}

プログラムを書き換えたら、改めてテストしてみましょう。「test result: ok. 1 passed;...」のように表示されたら成功です。

cargo test

プログラムを確認してみましょう。(＊1)と(＊2)の部分は何も変更していません。&strをVec<char>に変換して、is_match_slice関数を呼び出します。(＊3)の関数is_match_sliceでは、ワイルドカードのパターン「*」と「?」を利用したパターンマッチを行います。(＊4)では、先ほどのプログラムと同じように1文字ずつ文字を突き合わせてマッチするかを確認します。

ポイントとなるのが(＊5)のパターン「*」です。カーソルを1文字ずつ進めながら、マッチするかどうか関数is_match_sliceを再帰的に呼び出して確認します。カーソルを1文字分ずらしたスライスを作って、関数is_match_sliceを呼び出します。

(＊6)ではパターン「?」をマッチするか確認し、(＊7)ではワイルドカード以外のパターンを確認します。(＊8)ではパターンも対象文字列もカーソルが末尾に達したかを確認します。

(＊9)ではテストを記述します。ワイルドカードの「*」と「?」が正しく使えるかをテストするものです。

前回のファイル再帰検索で使ってみよう

それでは、前回作ったファイルの再帰検索プログラムで、自作のワイルドカードのライブラリを使うように改造してみましょう。ちょっと長くなってしまったので、プログラム全体をこちら(https://gist.github.com/kujirahand/45ecf1d475535187b1d7fc2cb0863253)にアップロードしました。

プログラムをビルドするには、ターミナルで下記のコマンドを実行します。すると、target/debugに実行ファイルが作成されます。使い方は、前回と同じです。

cargo build

まとめ - ワイルドカードの実装について

以上、ワイルドカードを実装するプログラムを作ってみました。再帰を利用することで、比較的簡単にワイルドカードを実装できることが分かったことでしょう。それでも、この方法はそれほど効率的という訳ではありません。

再帰を使わないでパターン「*」用のカーソルを用意して実装する方法や、動的計画法を使う方法でもパターンマッチを記述できます。いろいろな手法でワイルドカードを実装できるので、より効率的な手法を試してみると良いでしょう。

自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。技術書も多く執筆している。直近では、「実践力をアップする Pythonによるアルゴリズムの教科書(マイナビ出版)」「シゴトがはかどる Python自動処理の教科書(マイナビ出版)」「すぐに使える!業務で実践できる! PythonによるAI・機械学習・深層学習アプリのつくり方 TensorFlow2対応(ソシム)」「マンガでざっくり学ぶPython(マイナビ出版)」など。