超置換単語を楽に見つけたい ＞＜！
Feb 12 2019超置換単語(造語)というとても面白いものを†計算機の力†を使って探し出してみます
こんにちは。
僕は学校から帰ると毎日Twitterを開きます。今日も同じように眺めているとこんなツイートがありました。
「しかいしゃ」という文字列は
— ことう (@ktu162) February 11, 2019
鹿、貝、石、社、司会、開始、医者、歯科医師、会社、司会者 と
どこから読み始めてどこから読み終えても単語になります。
これの6文字verは果たしてあるのでしょうか。
面白いので、もちろん僕では頭が悪すぎるので計算機の力を使ってやってみます。
辞書データ
まずは辞書データが必要ですよね。日本語の単語がたくさん乗ってるやつ、これは音についてなのでできれば漢字ではない方が良いです。こんなものを探し求めて情報の海を彷徨っていると、こういったものが漂流しているのを見つけました。
ありがたく使わせていただきます。いただきます。
問題を再確認
さて、問題をもう一度見てみましょう。
どこからでもと言っても、１文字は考えなくて良いみたいです。先程の辞書データには１文字の単語が乗っていなかったので都合が良いですね。
「しかいしゃ」という文字列は
鹿、貝、石、社、司会、開始、医者、歯科医師、会社、司会者 と
どこから読み始めてどこから読み終えても単語になります。
これの6文字verは果たしてあるのでしょうか。
あと、小さな文字（ゃゅぁ...）ですが、これは先程の辞書データでは大文字で表現されています。これは都合が悪いですが、しょうが無いです。後でどうこうできればします。
アルゴリズムを考える
上手いものは分からなかったので、愚直なやつで行きます、。（競プロができれば一瞬で上手いものが出来るのかなぁ...）
まず、「ー」「ん」が入っているデータを取り除きます。1
そして、辞書データを文字列長でファイルに分けます divide.cpp。
できたら、探索するプログラムを書きます。
今回は以下のような手順でやろうと思います。
ただ、これだと下の方で重複がありますね、、メモ化するようにしましょう。
Def. 探したい超置換単語の長さをNとしておきます。
各単語の多さは
1. N文字の単語をループで回す。
例えば、「わんだふるらいふ」で説明します。
2. それぞれについて、N-1文字の２つの塊に分けることができます。
「わんだふるらいふ」 -> 「わんだふるらい」「んだふるらいふ」
3. これらをN-1文字の単語のファイルから探します。
4. なければ終了。あればそれぞれについて2から再帰的にもう一回。
では、入力した単語が超置換単語だった場合の計算量（最悪計算量）を考えましょう。
N-1文字の分け方が2つ、N-2文字では3つ...となるので、
こんな感じで考えて、$$1 + ... + N = \frac{N^2-N}{2}$$で、この内1とNが無い形なので$$f(N)=\frac{N^2-N}{2}-N-1=\frac{1}{2}(N^2-3N-2)$$回の単語検索が必要になるということです。探索はlogMで出来るので、全体的には$O(N^2\text{lg}M)$となります?（自信がない
実際に荒く計算してみましょう。
それぞれのファイルの単語数は以下のようになっていました。カッコ内には四捨五入$\circ$lgをかましたものを書いておきます。
それぞれの長さの単語の個数よって、それぞれ探索回数は
２文字 - 1923個 <11>
３文字 - 12452個 <13>
４文字 - 30810個 <15>
５文字 - 27405個 <15>
６文字 - 20840個 <14>
７文字 - 15197個 <14>
８文字 - 9151個 <13>
大体の探索回数となります（多分）。とても現実的ですね！
２文字 - 0回
３文字 - 22回
４文字 - 59回
５文字 - 113回
６文字 - 182回
７文字 - 264回
８文字 - 360回
コードを書く
今回は遅くなるかなぁと思ったのでC++で書きました2
と思いましたが、やっぱりPythonで書きました(ﾃﾍﾍﾟﾛ
実験で使用したコード類はGitHubに置いています。
結果
試しに6文字でやった所
が出力されました。これの検査は良いとして、
しゆうきよう
しゆうきよく
じゆうきよう
わいしようし
小書き文字を頭に来るときには普通に文字にして読むのであれば
— 主電源@ドラポ勢 (@adeleine_P) 2019年2月11日
「しゅうしょく(就職)」とかどうでしょう
しゅうしょく(就職)
主 週 終止 週初
夕 勇姿 郵書 夕食
牛 羽書 う蝕
署 職
欲
このようなツイートがあるにもかかわらず、私のポンコツなプログラムを食った計算機が人間に負けてしまっているというところが由々しいことです。
調べてみると、
「羽書」が含まれてない様です。
んー、、、辞書データを変えるか...とも思っていくつか見ましたが、羽書が含まれているものはありませんでした。
こうなったら人間と計算機の協力プレイだ！ということで、上の例のように１個だけアウトの物を書き出してめっちゃ頑張って調べたいと思います。
協力プレイをば
一個だけアウトのものを書き出すと
あいしようか あいちようか いけいしよう いじゆうしや いじようしや うきようしき うだいしよう うちゆうきち うちゆうきぼ えいきようか えいきようど えいじゆうち おしようすい かいきようき かいきようと かいきようぶ かいしゆうき かいしゆうび かいしようき かいしようほ かいちようば かがくしやく かすいしよう かどうきよう がいしようぶ きかいじゆう きぎようしや きせいじゆう きそうきよく きたいしよく きちようしや きないしよく きゆうきよう きゆうきよく きようかいか きようかいし きようかいち きようしやく きようじゆう きようじゆし きようじゆつ きようそうば きようどうか きろくしゆう ぎしようしや ぎやくしゆう ぎやくじよう ぎようかいご ぎようかいし くぎようそう くないしよう けいしようち けしようしつ けしようすい こうきようか こうきようし こうきようじ こうしやくし こけいしよく こししようじ こしようしや こちようそう こていじゆう こていちよう こばいしよう ごしようかい ごじようしや ごせいきよう ごせいしよう ごとうしやく ごないしよう さいきようぎ さいきようぶ さいしゆうず さいしゆうち さいしゆうび さいしゆうぶ さいしゆうり さいしゆうわ さいしようえ さいしようか さいしようじ さいしようち さいしようふ さいしよくが さいちようか さかいじゆう さきようしき さぎようしや さしようしや さだいしよう ざいがくしや ざいせいかい しがいしよく しけいしゆう しげきしゆう ししようしや しじようかい しじようしや しちようかい しちようしや していしよく してきしよう しやくじよう しやこうかい しゆうかくき しゆうしやく しようかいき しようかいは しようしやき しようしやく しようじゆう しようじゆつ しようそくし しようどうか しようどうし しようばいぎ しようばいや しようまいし じかいしよく じぎようかい じぎようしや じしようしき じじゆうだい じへいしよう じめいしよう じやくしゆう じやくじよう じゆうかいき じゆうきよし じゆうきよち じゆうきよひ じゆうだいけ じゆうだいし じゆうだいじ じようしきか じようしきは じようしつし じようしやく じようじゆう じようじゆつ じようそうび じようそうぶ じようどうえ じようどうじ すぎようしや せいきようか せいきようし せいきようと せいしゆうき せいしよくき せいとうしゆ せいぶつかい せかいじゆう せきしようも せきじゆうじ せきじようし せしゆうしや そうきよくし そしきじよう たいがくしや たいきよくず たいしゆうか たいしゆうし たいしようか たいしようき たいしよくか たいじゆうさ たいちようき たぎようかい たはいしよく だいがくしや だいしようじ だいしようり ちじようかい ちじようしや ちちゆうかい ちめいしよう ちやくしゆつ ちゆうかくし ちゆうかくは ちゆうかくぶ ちゆうきよう ちゆうしつし ちゆうしつゆ ちゆうしやき ちゆうしやく ちようかいひ ちようごうか ちようしやく ちようじゆう ちようじゆか ちようそくき ちようばいか ちりがくしや ていがくしや ていしゆうは ていしようひ ていしよくや ていじゆうち てきようしや てないしよく ときようそう とけいしゆう とけいしよう とちゆうかい どうしやくが どうちゆうき どちやくしゆ ならいしよう にじゆうだい にゆうきよう にゆうきよく はじようしや はれいしよう ばいしようふ ばいしようろ ばたいじゆう ばはいきよう ひしようしつ ひじようしき ひたいしよう ひだいしよう ひやくしゆつ びちゆうかく ふかいしゆう ふきようしや ふくしゆうき ふくじゆうき ふしようしや ふせいしよう ふていしよう ふていちよう ふとうかいこ ふはいしゆう ふふくじゆう ぶたいちよう ぶちようかい へいがくしや ほうしやくじ ほどうきよう みかいしゆう みちやくしゆ みようじゆう みようじゆつ むきようしつ むきようそう むぎようしや むさいしよく むそうきよく むばいしよう めいしようち めいしようぶ めいちようし やくじようび やそうきよく ゆうきようひ らいちようか りそうきよう りゆうきよく るけいしゆう れきしようご ろうきよくか ろうきよくし ろこうきよう わいしようか わかいしゆう結構たくさんありました (268単語？)
それぞれ、足りない文字を色々頑張って見つけると、案外あるので、６文字ではなく、７文字・８文字を探すことにしました。
高み
意気込んだは良いものの、７文字は一つも出てきませんでした。１単語の猶予を与えても出てこず...２単語の猶予を与えると、９個の単語が出てきました。
８文字に関しては５単語の猶予も見てみましたがなかなかありませんでした。
６文字は沢山あるので、７文字を協力プレイで探しました。
まとめ
６文字はめっちゃありますが、一応答として一例を。
他の物もここらへんを中心に探してみればザクザク見つかると思います。
あいしょうか 愛傷歌, 相性, 愛書, 哀史, 愛, 医師, 書, 衣装, 陽, 胃小窩
７文字に関しては、ありませんでした。頑張って探しましたがあの辞書と僕の協力プレイの限りは無いです。
惜しかったのとしては、
でした。
がいしょうしゃ
けいしょうしゃ
たいしょうしゃ
ていしょうしゃ
ないしょうしゃ
しゅうきょうし
じゅうきょうど
むしゅうきょう
特に上の方にある「〜いしょうしゃ」は「いしょうしゃ」だけが見つからないものが多くてとても惜しい！って感じですね。
楽しかったです。やはり計算機の力は凄いなぁ...(探索をしただけ
Notes
1 「ー」「ん」から始まる単語が無いので ↩
2 計算量を考える前に決めたんです。Pythonでも良かったなぁ... ↩
