C++で解く最小単語分割（Minimum Word Break）問題：トライ木による効率的な実装

任意のサイズの単語からなる文字列配列が与えられたとき、その連結文字列をあらゆる方法で分割し、分割後の各部分がすべて有効な単語になるようにすることを考えます。そのような分割の中で、必要となる最小の分割回数を求めるのが本問題の目的です。

まず、具体的な入出力シナリオを見てみましょう。

入出力の例

入力 − string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }

出力 − 最小単語分割数：1

説明 − 複数の単語が与えられています。ここで、「Hell」と「all」という2つの文字列を連結した「Hellall」を渡し、これを分割します。「Hellall」は「Hell all」と分割でき、これが最初の分割となり、両方とも有効な単語です。さらに細かく分割しても、たとえば「He ll aa」のような無効な文字列しか得られません。したがって、出力は1となります。

入力 − string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }

出力 − 最小単語分割数：1

説明 − 今度は「Hell」と「well」を連結した「Hellwell」を渡します。これは「Hell well」と分割でき、この1回の分割で両方とも有効な単語になります。さらに「He ll well」のように分割しても有効な文字列は得られません。よって、出力は1です。

プログラムで使用している手法

本プログラムでは、単語を高速に照会できるようトライ木（前方一致木）と呼ばれる木構造を構築し、再帰的な探索によって最小分割数を求めます。大まかな流れは以下の通りです。

• 単語の文字列配列を入力し、size() 関数で配列のサイズを取得します。

• 変数 min_val を宣言し、最大値を表す INT_MAX で初期化します。

• 構造体 node 型のオブジェクト root を作成し、Return_Node() の呼び出し結果で初期化します。

• i = 0 から配列サイズまで FOR ループを回し、その中で Insert_Node() を呼び出してツリーにノードを挿入します。

• Minimum_Break() を呼び出して可能な最小の単語分割数を計算し、最終結果を出力します。

• 単語をデータとして持つノードのツリーを構築するための構造体を宣言します。

  • ポインタ配列 ptr[total_Alpha] と bool 型変数 check を作成します。

• Return_Node(void) の内部処理

  • 構造体へのポインタ ptr_1 を作成し、ptr_1->check を false に設定します。

  • i = 0 から i < total_Alpha まで FOR ループを回し、ループ内で ptr_1->ptr[i] を NULL に設定します。

  • ptr_1 を返します。

• Insert_Node(struct node* root, string val) の内部処理

  • ポインタ ptr_1 を作成し、root に設定します。

  • i = 0 から val.length() まで FOR ループを回し、key を val[i] - 'a' とします。もし ptr_1->ptr[key] が NULL であれば、Return_Node() の呼び出し結果を ptr_1->ptr[key] に設定します。

  • ptr_1 を ptr_1->ptr[key] に更新して進め、最後に ptr_1->check を true に設定します。

• Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0) の内部処理

  • ポインタ ptr_1 を作成し、root に設定します。

  • first == val.length() であるかを判定し、成立していれば *temp を C++ の組み込み関数 min(*temp, a - 1) の結果で更新して処理を終了します。

  • i = first から i < val.length() まで FOR ループを回し、address を val[i] - 'a' とします。もし ptr_1->ptr[address] が NULL なら return します。

  • ptr_1->ptr[address]->check が true であれば、Minimum_Break(root, val, i + 1, temp, a + 1) を再帰的に呼び出します。

  • ptr_1 を ptr_1->ptr[address] に更新します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define total_Alpha 26
//create a tree of nodes of words
struct node{
   struct node* ptr[total_Alpha];
   bool check;
};
//Return tree with all nodes
struct node* Return_Node(void){
   struct node* ptr_1 = new node;
   ptr_1->check = false;
   for (int i = 0; i < total_Alpha; i++){
      ptr_1->ptr[i] = NULL;
   }
   return ptr_1;
}
//insert values to the nodes in a tree
void Insert_Node(struct node* root, string val){
   struct node* ptr_1 = root;

   for(int i = 0; i < val.length(); i++){
      int key = val[i] - 'a';
      if(!ptr_1->ptr[key]){
         ptr_1->ptr[key] = Return_Node();
      }
      ptr_1 = ptr_1->ptr[key];
   }
   ptr_1->check = true;
}
//calculate the minimum word break
void Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0){
   struct node* ptr_1 = root;
   if(first == val.length()){
      *temp = min(*temp, a - 1);
      return;
   }
   for(int i = first; i < val.length(); i++){
      int address = val[i] - 'a';
      if(!ptr_1->ptr[address]){
         return;
      }
      if(ptr_1->ptr[address]->check){
         Minimum_Break(root, val, i + 1, temp, a + 1);
      }
      ptr_1 = ptr_1->ptr[address];
   }
}
int main(){
   string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" };
   int size = sizeof(word) / sizeof(word[0]);
   int min_val = INT_MAX;
   struct node* root = Return_Node();
   for (int i = 0; i < size; i++){
      Insert_Node(root, word[i]);
   }
   Minimum_Break(root, "Hellall", 0, &min_val, 0);
   cout<<"Minimum Word Break is: "<< min_val;
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

Minimum Word Break is: 1