C++で最長しりとりを全探索してみた

# はじめに
アルゴリズムの勉強も兼ねて、日本語で最長しりとりを全探索で解くプログラムを作成しました。動作環境はmacとしています(`<codecvt>`の関係上)。
フルソースコードは[こちら](https://github.com/ysuzuki19/YSL/blob/master/include/ShiriTree.hpp)まとめてあり、同リポジトリにテストも作成してあるので、興味がある方は試してみてください。
また、書き殴った感じで雑なので問題が起こったときの責任はおいかねますが、クラスにしてあるので自由に改変してどうぞ。

```plaintext:実行の流れ
1. `main.cpp`をコピーしてmac(ubuntuは非対応)でコンパイル
2. 最長しりとりを解きたい単語集をcsvに保存(word1, word2, ...というファイル)
3. 保存したcsvのファイル名をコマンドライン引数として実行
```

ターミナルで以下を行うと実行できます。

```bash:実行方法
$ git clone https://github.com/ysuzuki19/YSL
$ cd ./YSL/test/shiritree_test
$ make
$ ./proj <path_to_words_csv>
```

# 今回の反省
全探索でありかつ単純な深さ優先探索であるため、計算時間が膨大($O(n!)$かな？)となってしまった。
そのため、100文字を超えるデータを扱う場合はあまり有効ではない。
`std::string`→`std::wstring`への変換に手間取ってしまった上、`<codecvt>`を用いたためあまり良いプログラムではないしUbuntuでは実行不可能でmacだとなぜか動作する。暇な時に変更する予定。
また、全単語をあらかじめソートしているので、連結可能文字を調べるためには２分探索の方がよいかと模索中。

# 処理の流れ

```plaintext:アルゴリズム
1. csvをロード
2. 全単語をソート
3. 全単語の先頭・末尾のみを抽出し、さらに`が→か`や`ャ→ヤ`のように濁音・半濁音・小文字を大文字no濁音に変換。このとき、`ー`であれば１つ前の文字を末尾とする。
4. 探索開始
    4.1. 全単語が開始文字となるまでループ
        4.1.1. 未使用であり最後の単語に接続可能な単語を見つける
        4.1.2. 該当単語を使用済みにする
        4.1.3. 現在の連結単語数が最大であれば、各値を更新
        4.1.3. (4.1.*)を再帰(DFS)
        4.1.4. 該当単語を未使用に戻す
        4.1.5. 該当単語がなくなるまで探索
5. 探索終了
```

# コードの断片と解説

## 使用ヘッダ
ここは箇条書きで記す。

- `iosream`:標準出力のため
- `fstream`:ファイル入出力のため
- `sstream`:ファイルロード時にカンマで区切るため
- `vector` :データを管理するため（クラス内で用いたくはないが今回の本題ではないので使用）
- `string` :入力文字列を保存・出力するため
- `codecvt`:`std::string→std::wstring`変換のため（非推奨のため本来は使うべきではない）

```cpp:
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <codecvt>
```

## クラス全体
`YSL`は名前空間を汚さないために名付けた。木の探索っぽかったので、`shiritori + tree`→`shiritree`と名付けた。`YSL::ShiriTree::shiritree_word_`は、各単語を格納するクラスであり、これに関しては後述する。

#### プライベート変数・関数の概要
`shiritree`の内部で行われる処理に用いられる変数および、外部から呼び出す必要のない（と思われる）関数である。
簡単のため、表にて機能を示す。

|変数・関数名|機能|
|---|---|
|`std::vector<std::string> string_words_`|csvから読み取った単語をそのまま格納（結果出力用）|
|`std::vector<shiritree_word_> shiritree_words_`|アルゴリズム内で主に使用する変数（詳細は後述）|
|`std::vector<std::size_t> continuous_idx_`|探索時の連結単語のインデックス番号（増減する）|
|`std::vector<std::size_t> max_continuous_idx_`|探索過程における最大連結単語のインデックス番号（増加する）|
|`std::string spaces_for_print_`|`¥r`で出力する際に単語がはみ出ない様調整するためスペースを数個持つ文字列|
|`std::size_t words_count_`|csvロード時にカンマの個数から単語数を計算|
|`std::size_t now_length_`|探索時の連結単語数（増減する）|
|`std::size_t max_length_`|探索過程における最大連結単語数（増加する）|
|`bool logging_`|ログ出力をするかをヘッダ外から指定するフラグ（デフォルトでは`true`）|
|`void dfs()`|再帰用の深さ優先探索関数|
|`inline void log_print(std::string str) const`|ログ出力用の関数|
|`inline void log_print_r(std::string str) const`|ログ出力用の関数(改行→'¥r')|

#### パブリック関数の概要
変数のアクセサ・データロード・探索開始・ログ出力設定・結果出力に対する関数をいくつか用意した。
簡単のため、表にて機能を示す。

|変数・関数名|機能|
|---|---|
|`shiritree()`|デフォルトコンストラクタであり、何もしない|
|`shiritree(std::string filename)`|入力ファイルから単語集をロードする機能を持つコンストラクタであり、`load()`を呼び出す|
|`void load(std::string filename)`|入力ファイル(.csv)から単語集をロードする|
|`void solve()`|深さ優先探索によって最長しりとりを求める|
|`inline void view_words() const`|ソート済み全単語を標準出力|
|`inline void view_continuous_words() const`|最大連結単語を標準出力|
|`void output(std::string filename) const`|引数のファイル名に連結単語を出力|
|`void report(std::string filename) const`|引数のファイルに入力・出力・入力単語数・最大連結単語数・連結レートを出力|
|`inline std::size_t length() const noexcept`|最大連結単語数を返す|
|`inline void setLogging(bool flag) noexcept`|ログ出力するか設定する|
|`inline bool getLogging() const noexcept`|ログ出力の有無を確認する|
|`inline std::size_t wordSize() const noexcept`|入力単語数を返す|
|`inline double usageRate() const`|連結レート($最大連結単語数/入力単語数$)を返す|

以下、該当部のコード

```cpp:
namespace YSL{
  class shiritree {
    class shiritree_word_{
      /* １単語を格納するクラス。ここは後述する */
    };
    private:
      std::vector<std::string> string_words_;
      std::vector<shiritree_word_> shiritree_words_;
      std::vector<std::size_t> continuous_idx_;
      std::vector<std::size_t> max_continuous_idx_;
      std::string spaces_for_print_ = "";
      std::size_t words_count_ = 0;
      std::size_t now_length_ = 0;
      std::size_t max_length_ = 0;
      bool logging_ = true;
    public:
      shiritree(){}
      shiritree(std::string filename){ load(filename); }
      void load(std::string filename);
      void dfs();
      void solve();
      inline void view_words() const;
      inline void view_continuous_words() const;
      void output(std::string filename) const;
      void report(std::string filename) const;
      inline std::size_t length() const noexcept { return max_length_; }
      inline void setLogging(bool flag) noexcept { logging_ = flag; }
      inline bool getLogging() const noexcept { return logging_; }
      inline std::size_t wordSize() const noexcept { return words_count_; }
      inline double usageRate() const { return (double)max_length_/(double)words_count_; }
      inline void log_print(std::string str) const;
      inline void log_print_r(std::string str) const;
  };
}
```

## １単語格納用クラス`shiritree_word_`
当クラスは、`YSL::ShiriTree`の内部のアルゴリズムの内部で必要な機能を有するプライベートなクラスである。
こちらでも簡単のため表にて機能を示す。

|メンバ|機能|
|---|---|
|`std::wstring wstr_`|マルチバイト単語を格納（入力単語のうち１つ）|
|`bool isUse_`|単語がしりとりに組み込まれているかを記憶するフラグ|
|`wchar_t first_letter_`|マルチバイトにした単語の先頭文字を格納|
|`wchar_t last_letter_`|マルチバイトにした単語の末尾文字を格納（ただし、大文字no濁点としつつ`ー`は前語を扱う）|
|`wchar_t to50Letters(wchar_t ch)`|濁点・半濁点・小文字を大文字no濁点の文字に変換する|
|`shiritree_word_()`|デフォルトコンストラクタ|
|`shiritree_word_(std::string str)`|格納する単語を準備するコンストラクタ|
|`void setString(std::string str)`|格納する単語を設定する|
|`inline std::wstring getString() const noexcept`|格納された単語を返す|
|`inline bool isUse() const noexcept`|単語がしりとりに含まれているか返す|
|`inline void setUse(bool flag)`|単語の使用状況を変更する|
|vinline wchar_t first() const noexcept`|単語の先頭文字を返す|
|`inline wchar_t last() const noexcept`|単語の末尾文字を返す|

以下、該当部のコードである。

```cpp:
    class shiritree_word_{
      private:
        std::wstring wstr_ = L"       ";
        bool isUse_ = false;
        wchar_t first_letter_ = L' ';
        wchar_t last_letter_ = L' ';
        wchar_t to50Letters(wchar_t ch){
          constexpr wchar_t from_kata[30] = L"ガギグゲゴザジズゼゾダヂヅデドバビブベボパピプペポィャュョ";
          constexpr wchar_t to_kata[30]   = L"カキクケコサシスセソタチツテトハヒフヘホハヒフヘホイヤユヨ";
          for(int i=0; i<30; ++i) if(ch == from_kata[i]) return to_kata[i];
          constexpr wchar_t from_hira[30] = L"がぎぐげござじずぜぞだぢづでどばびぶべぼぱぴぷぺぽぃゃゅょ";
          constexpr wchar_t to_hira[30]   = L"かきくけこさしすせそだちつてとはひふへほはひふへほいやゆよ";
          for(int i=0; i<30; ++i) if(ch == from_hira[i]) return to_hira[i];
          return ch;
        }
      public:
        shiritree_word_() { }
        shiritree_word_(std::string str) { setString(str); }
        void setString(std::string str) {
          std::wstring_convert<std::codecvt_utf8<wchar_t>,wchar_t> cvt;
          wstr_ = cvt.from_bytes(str);
          first_letter_ = to50Letters(wstr_[0]);
          if(wstr_[wstr_.size()-1] == L'ー') last_letter_ = to50Letters(wstr_[wstr_.size()-2]);
          else if(wstr_[wstr_.size()-1] == L'ー') last_letter_ = to50Letters(wstr_[wstr_.size()-2]);
          else last_letter_ = to50Letters(wstr_[wstr_.size()-1]);
        }
        inline std::wstring getString() const noexcept { return wstr_; }
        inline bool isUse() const noexcept { return isUse_; }
        inline void setUse(bool flag) { isUse_ = flag; }
        inline wchar_t first() const noexcept { return first_letter_; }
        inline wchar_t last() const noexcept { return last_letter_; }
    };
```

### 複数行にまたがる関数の説明
#### wchar_t to50Letters(wchar_t ch)
濁音・半濁音・小文字をすべて50音に修正する関数。まずはカタカナを修正した後、ひらがなについても修正。どちらも該当しない場合は引数をそのまま返す。

```cpp:
wchar_t to50Letters(wchar_t ch){
  constexpr wchar_t from_kata[30] = L"ガギグゲゴザジズゼゾダヂヅデドバビブベボパピプペポィャュョ";
  constexpr wchar_t to_kata[30]   = L"カキクケコサシスセソタチツテトハヒフヘホハヒフヘホイヤユヨ";
  for(int i=0; i<30; ++i) if(ch == from_kata[i]) return to_kata[i];
  constexpr wchar_t from_hira[30] = L"がぎぐげござじずぜぞだぢづでどばびぶべぼぱぴぷぺぽぃゃゅょ";
  constexpr wchar_t to_hira[30]   = L"かきくけこさしすせそだちつてとはひふへほはひふへほいやゆよ";
  for(int i=0; i<30; ++i) if(ch == from_hira[i]) return to_hira[i];
  return ch;
}
```

#### void setString(std::string str)
`std::string`を`std::wstring`に変換しつつ、クラスのメンバに格納する関数である。ここでは、非推奨であるが`std::wstring_convert<>`を用いて変換している。変換して代入した後、先頭文字・末尾文字についても格納する。
先頭文字については、`to50Letters()`を呼び出すだけで良い。末尾文字については、`ー`or`ー`である時には例外として末尾の１つ前の文字を`to50Letters()`で変換し格納する。

```cpp:
void setString(std::string str) {
  std::wstring_convert<std::codecvt_utf8<wchar_t>,wchar_t> cvt;
  wstr_ = cvt.from_bytes(str);
  first_letter_ = to50Letters(wstr_[0]);
  if(wstr_[wstr_.size()-1] == L'ー') last_letter_ = to50Letters(wstr_[wstr_.size()-2]);
  else if(wstr_[wstr_.size()-1] == L'ー') last_letter_ = to50Letters(wstr_[wstr_.size()-2]);
  else last_letter_ = to50Letters(wstr_[wstr_.size()-1]);
}
```

## `shiritree`のメンバ関数の説明
#### void dfs()
深さ優先探索処理時の再帰用関数。設定により、ログ出力を行う。探索時の連結文字数が、過去の連結文字数を上回る事に、連結情報を更新する。
その後、末尾文字が`ン`or`ん`である場合、関数は終了。そうでなければ、現在の単語の末尾文字と同一の先頭文字であり未使用の単語を見つけて当関数を再帰する。

```cpp:
void dfs(){
  log_print_r("seaching lenth : " + std::to_string(now_length_) + "  last word : " + string_words_[continuous_idx_[now_length_-1]]);
  if(now_length_ > max_length_){
    log_print("now lenth is " + std::to_string(now_length_));
    if(logging_) view_continuous_words();
    max_length_ = now_length_;
    max_continuous_idx_ = continuous_idx_;
  }
  if(shiritree_words_[continuous_idx_[now_length_-1]].last() == L'ン') return;
  if(shiritree_words_[continuous_idx_[now_length_-1]].last() == L'ん') return;
  for(std::size_t i=0; i<shiritree_words_.size(); ++i){
    if(!shiritree_words_[i].isUse()){
      if(shiritree_words_[i].first() == shiritree_words_[continuous_idx_[now_length_-1]].last()){
        continuous_idx_[now_length_] = i;
        now_length_++;
        shiritree_words_[i].setUse(true);
        dfs();
        shiritree_words_[i].setUse(false);
        now_length_ --;
      }
    }
  }
}
```

#### inline void log_print(std::string str) const
ログの設定によりログ出力を行う関数。

```cpp:
inline void YSL::ShiriTree::log_print(std::string str) const {
  if(logging_) std::cout << "[LOG] " << str << spaces_for_print_ << std::endl;
}
```
#### inline void log_print_r(std::string str) const
ログの設定によりログ出力を、末尾をキャリッジリターンとして行う関数。これにより、ログ出力をきれいに動きを出すことができる。

```cpp:
inline void YSL::ShiriTree::log_print_r(std::string str) const {
  if(logging_) std::cout << "[LOG] " << str << spaces_for_print_ << "\r";
}
```

#### void load(std::string filename)
引数を名前にもつファイル(csv)をロードし、データを準備する。本関数は、コンストラクタによって呼び出されることがある。
`ifstream`によってファイルを開いてファイル全体を読み込み、カンマ`,`の個数から単語数を読み込み、各変数への代入を開始する。
また、`shiritree_word_`クラスへの値の代入もここで完了する。

```cpp:
void YSL::ShiriTree::load(std::string filename){
  log_print("Loading words by " + filename);
  std::ifstream fin(filename);
  {
    std::string row_data;
    std::getline(fin, row_data);
    words_count_ = count(row_data.begin(), row_data.end(), ',') + 1;
    string_words_.resize(words_count_);
    std::stringstream ss(row_data);
    for(std::size_t i=0; i<words_count_; ++i) std::getline(ss, string_words_[i], ',');
    std::sort(string_words_.begin(), string_words_.end());
    shiritree_words_.resize(words_count_);
    std::size_t max_strlen = 0;
    for(std::size_t i=0; i<words_count_; ++i){
      max_strlen = std::max(max_strlen, string_words_[i].length());
      shiritree_words_[i].setString(string_words_[i]);
    }
    spaces_for_print_.resize(max_strlen*2, ' ');
    continuous_idx_.resize(words_count_);
  }
  return;
}
```

#### void solve()
探索開始の関数。当関数は、再帰されずに、`dfs()`関数を呼び出す役割を持つ。これは、連結の最初の単語は例外として、全単語に対して探索するためである。

```cpp:
void YSL::ShiriTree::solve(){
  log_print("Solver is started.");
  now_length_ = 0;
  max_length_ = 0;
  for(std::size_t i=0; i<shiritree_words_.size(); ++i){
    continuous_idx_[0] = i;
    now_length_++;
    shiritree_words_[i].setUse(true);
    dfs();
    shiritree_words_[i].setUse(false);
    now_length_--;
  }
  log_print("Solver is finished.");
}
```

#### inline void view_words() const
連結にかかわらず、ソートされた単語をすべて標準出力する。

```cpp:
inline void YSL::ShiriTree::view_words() const {
  for(const auto& e : string_words_) std::cout << e << " ";
  std::cout << std::endl;
  return;
}
```
#### inline void view_continuous_words() const
連結単語をすべて標準出力する。

```cpp:
inline void YSL::ShiriTree::view_continuous_words() const {
  for(std::size_t i=0; i<max_length_; ++i){
    std::cout << string_words_[max_continuous_idx_[i]] << " ";
  }
  std::cout << std::endl;
  return;
}
```

#### void output(std::string filename) const
しりとりの結果を引数のファイルに出力する。

```cpp:
void YSL::ShiriTree::output(std::string filename) const {
  log_print("Outputing file by " + filename);
  std::ofstream fout(filename);
  fout << max_length_ << " words connected." << std::endl;
  for(std::size_t i=0; i<max_length_; ++i){
    fout << string_words_[continuous_idx_[i]] << " ";
  }
  fout << std::endl;
  return;
}
```

#### void report(std::string filename) const
しりとりの結果および以下の各情報を引数のファイルに出力する。

- 読み込み単語数
- 連結単語数
- 連結レート
- 読み込み全単語
- 連結全単語

```cpp:
void YSL::ShiriTree::report(std::string filename) const {
  log_print("Reporting to " + filename);
  std::ofstream fout(filename);
  fout << "Loaded    Words Length : " << wordSize() << std::endl;
  fout << "Connected Words Length : " << length() << std::endl;
  fout << "Words Usage Rate        : " << usageRate() << std::endl;
  fout << "-- Loaded Words ------------------------------------------" << std::endl;
  for(std::size_t i=0; i<string_words_.size(); ++i){
    fout << string_words_[i] << " ";
  }
  fout << std::endl;
  fout << "-- Connected Words ---------------------------------------" << std::endl;
  for(std::size_t i=0; i<max_length_; ++i){
    fout << string_words_[continuous_idx_[i]] << " ";
  }
  fout << std::endl;
  fout << "----------------------------------------------------------" << std::endl;
  return;
}
```


## 使用例
インクルードに関しては上述したため省略する。クラスをそのままコードに書くかヘッダとしてインクルードすることで利用することができる。

```cpp:main.cpp
#include <iosteam>
#include "../../include/ShiriTree.hpp"
using namespace std;

int main(int argc, char *argv[]){
  wcout.imbue(std::locale("en_US.UTF-8"));
  std::string filename;
  if(argc == 2){
    filename = argv[1];
    std::cout << "[LOG] filename to shiritree : " << filename << std::endl;
  }else{
    std::cout << "[ERROR] Please input argv[1] : filename to shiritree." << std::endl;
    return 0;
  }
  YSL::ShiriTree shiritori;
  shiritori.load(filename);
  cout << "Loaded Words List " << endl;
  //shiritori.setLogging(false);
  shiritori.view_words();
  shiritori.solve();
  cout << "Loaded     Words Length : " << shiritori.wordSize() << endl;
  cout << "Continuous Words Length : " << shiritori.length() << endl;
  cout << "Words Usage Rate        : " << shiritori.usageRate() << endl;
  shiritori.view_continuous_words();
  shiritori.report("result.txt");
  return 0;
}
```

# おわりに
使用するすべての単語に対して全探索を行っているため処理が遅くなってしまったので、複数単語をまとめる処理（pre連結）を加えることで高速化できるのではと考えています。(例 `きーた＋たんさく`→`きた＋たく`→`きく`)