C++でリスト内の全単語の最短一意プレフィックスを求めるアルゴリズム

問題概要

この問題では、単語の配列 arr[] が与えられ、リスト内のすべての単語について「最短の一意のプレフィックス(接頭辞)」を求めることが課題となります。ここでいう一意のプレフィックスとは、他のどの単語の接頭辞にもならない、その単語だけを識別できる最短の文字列のことです。

入力例

arr[] = {"learn", "programming", "code", "leap"}

出力例

c
leap
lear
p

この例では、「code」は先頭の1文字「c」だけで他の単語と区別でき、「programming」も同様に「p」だけで十分です。一方、「learn」と「leap」は先頭の「lea」までが共通しているため、それぞれ「lear」「leap」というより長いプレフィックスが必要になります。

解法アプローチ

最も単純な解法は、各単語のすべてのプレフィックスを順に生成し、それが配列内の他の単語のプレフィックスと一致しない最初のものを見つけるというものです。しかし、この方法は計算量が大きくなり、非効率です。

そこで有効なのが、トライ木(trie)データ構造を利用する効率的なアプローチです。手順は以下の通りです。

1. すべての単語をトライ木に挿入して構築する。
2. 挿入処理の際に、各ノードが通過された回数(頻度)を記録する。
3. 各単語について根から対応するノードまでの経路をたどり、頻度が1になるノードに到達した時点までの文字列を出力する。それがその単語の最短の一意のプレフィックスとなる。

この手法では、挿入と探索の両方が単語長に比例した時間で行えるため、全体の計算量は O(n × L)(n は単語数、L は最大単語長)となり、非常に効率的です。

C++での実装例

以下は、上記の解法を実装したプログラムです。

#include<iostream>
using namespace std;
#define MAX 256
struct trieNode {
    struct trieNode *child[MAX];
    int freq;
};
struct trieNode *newTrieNode(void){
    struct trieNode *newNode = new trieNode;
    newNode->freq = 1;
    for (int i = 0; i<MAX; i++)
        newNode->child[i] = NULL;
    return newNode;
}
void insert(struct trieNode *root, string str) {
    int len = str.length();
    struct trieNode *pCrawl = root;
    for (int level = 0; level<len; level++) {
        int index = str[level];
        if (!pCrawl->child[index])
            pCrawl->child[index] = newTrieNode();
        else
            (pCrawl->child[index]->freq)++;
        pCrawl = pCrawl->child[index];
    }
}
void findShortestUniquePrefixRec(struct trieNode *root, char prefixChar[], int ind) {
    if (root == NULL)
        return;
    if (root->freq == 1) {
        prefixChar[ind] = '\0';
        cout<<prefixChar<<endl;
        return;
    }
    for (int i=0; i<MAX; i++) {
        if (root->child[i] != NULL) {
            prefixChar[ind] = i;
            findShortestUniquePrefixRec(root->child[i], prefixChar, ind+1);
        }
    }
}
void findShortestUniquePrefix(string arr[], int n) {
    struct trieNode *root = newTrieNode();
    root->freq = 0;
    for (int i = 0; i<n; i++)
        insert(root, arr[i]);
    char prefixChar[250];
    findShortestUniquePrefixRec(root, prefixChar, 0);
}
int main() {
    string arr[] = {"learn", "programming", "code", "leap"};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"All Shortest unique prefix for every words in a given list are : \n";
    findShortestUniquePrefix(arr, n);
    return 0;
}

実行結果

All Shortest unique prefix for every words in a given list are −
c
leap
lear
p

まとめ

トライ木を活用することで、各ノードの通過回数を記録しながら単語を登録し、頻度が1のノードに到達した時点でプレフィックスを確定できるため、総当たり方式と比べて大幅に高速に最短一意プレフィックスを求められます。オートコンプリートや検索候補の表示など、プレフィックスマッチングが必要な場面で応用できる有用なテクニックです。