超置換単語を楽に見つけたい ><!

Feb 12 2019

超置換単語(造語)というとても面白いものを†計算機の力†を使って探し出してみます

こんにちは。

僕は学校から帰ると毎日Twitterを開きます。今日も同じように眺めているとこんなツイートがありました。

面白いので、もちろん僕では頭が悪すぎるので計算機の力を使ってやってみます。

辞書データ

まずは辞書データが必要ですよね。日本語の単語がたくさん乗ってるやつ、これは音についてなのでできれば漢字ではない方が良いです。こんなものを探し求めて情報の海を彷徨っていると、こういったものが漂流しているのを見つけました。

【非公式】豚辞書 第14版【再頒布】

ありがたく使わせていただきます。いただきます。

問題を再確認

さて、問題をもう一度見てみましょう。


「しかいしゃ」という文字列は
鹿、貝、石、社、司会、開始、医者、歯科医師、会社、司会者 と
どこから読み始めてどこから読み終えても単語になります。
これの6文字verは果たしてあるのでしょうか。

どこからでもと言っても、1文字は考えなくて良いみたいです。先程の辞書データには1文字の単語が乗っていなかったので都合が良いですね。

あと、小さな文字(ゃゅぁ...)ですが、これは先程の辞書データでは大文字で表現されています。これは都合が悪いですが、しょうが無いです。後でどうこうできればします。

アルゴリズムを考える

上手いものは分からなかったので、愚直なやつで行きます、。(競プロができれば一瞬で上手いものが出来るのかなぁ...)

まず、「ー」「ん」が入っているデータを取り除きます。1

そして、辞書データを文字列長でファイルに分けます divide.cpp

できたら、探索するプログラムを書きます。

今回は以下のような手順でやろうと思います。



Def. 探したい超置換単語の長さをNとしておきます。
各単語の多さは

1. N文字の単語をループで回す。
例えば、「わんだふるらいふ」で説明します。
2. それぞれについて、N-1文字の2つの塊に分けることができます。
「わんだふるらいふ」 -> 「わんだふるらい」「んだふるらいふ」
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をかましたものを書いておきます。

それぞれの長さの単語の個数 

2文字 - 1923個 <11>
3文字 - 12452個 <13>
4文字 - 30810個 <15>
5文字 - 27405個 <15>
6文字 - 20840個 <14>
7文字 - 15197個 <14>
8文字 - 9151個 <13>

よって、それぞれ探索回数は

大体の探索回数 

2文字 - 0回
3文字 - 22回
4文字 - 59回
5文字 - 113回
6文字 - 182回
7文字 - 264回
8文字 - 360回

となります(多分)。とても現実的ですね!

コードを書く

今回は遅くなるかなぁと思ったのでC++で書きました2

と思いましたが、やっぱりPythonで書きました(テヘペロ

実験で使用したコード類はGitHubに置いています。

結果

試しに6文字でやった所



しゆうきよう
しゆうきよく
じゆうきよう
わいしようし

が出力されました。これの検査は良いとして、

このようなツイートがあるにもかかわらず、私のポンコツなプログラムを食った計算機が人間に負けてしまっているというところが由々しいことです。

調べてみると、

「羽書」が含まれてない様です。

んー、、、辞書データを変えるか...とも思っていくつか見ましたが、羽書が含まれているものはありませんでした。

こうなったら人間と計算機の協力プレイだ!ということで、上の例のように1個だけアウトの物を書き出してめっちゃ頑張って調べたいと思います。

協力プレイをば

一個だけアウトのものを書き出すと

結構たくさんありました (268単語?)

あいしようか

あいちようか

いけいしよう

いじゆうしや

いじようしや

うきようしき

うだいしよう

うちゆうきち

うちゆうきぼ

えいきようか

えいきようど

えいじゆうち

おしようすい

かいきようき

かいきようと

かいきようぶ

かいしゆうき

かいしゆうび

かいしようき

かいしようほ

かいちようば

かがくしやく

かすいしよう

かどうきよう

がいしようぶ

きかいじゆう

きぎようしや

きせいじゆう

きそうきよく

きたいしよく

きちようしや

きないしよく

きゆうきよう

きゆうきよく

きようかいか

きようかいし

きようかいち

きようしやく

きようじゆう

きようじゆし

きようじゆつ

きようそうば

きようどうか

きろくしゆう

ぎしようしや

ぎやくしゆう

ぎやくじよう

ぎようかいご

ぎようかいし

くぎようそう

くないしよう

けいしようち

けしようしつ

けしようすい

こうきようか

こうきようし

こうきようじ

こうしやくし

こけいしよく

こししようじ

こしようしや

こちようそう

こていじゆう

こていちよう

こばいしよう

ごしようかい

ごじようしや

ごせいきよう

ごせいしよう

ごとうしやく

ごないしよう

さいきようぎ

さいきようぶ

さいしゆうず

さいしゆうち

さいしゆうび

さいしゆうぶ

さいしゆうり

さいしゆうわ

さいしようえ

さいしようか

さいしようじ

さいしようち

さいしようふ

さいしよくが

さいちようか

さかいじゆう

さきようしき

さぎようしや

さしようしや

さだいしよう

ざいがくしや

ざいせいかい

しがいしよく

しけいしゆう

しげきしゆう

ししようしや

しじようかい

しじようしや

しちようかい

しちようしや

していしよく

してきしよう

しやくじよう

しやこうかい

しゆうかくき

しゆうしやく

しようかいき

しようかいは

しようしやき

しようしやく

しようじゆう

しようじゆつ

しようそくし

しようどうか

しようどうし

しようばいぎ

しようばいや

しようまいし

じかいしよく

じぎようかい

じぎようしや

じしようしき

じじゆうだい

じへいしよう

じめいしよう

じやくしゆう

じやくじよう

じゆうかいき

じゆうきよし

じゆうきよち

じゆうきよひ

じゆうだいけ

じゆうだいし

じゆうだいじ

じようしきか

じようしきは

じようしつし

じようしやく

じようじゆう

じようじゆつ

じようそうび

じようそうぶ

じようどうえ

じようどうじ

すぎようしや

せいきようか

せいきようし

せいきようと

せいしゆうき

せいしよくき

せいとうしゆ

せいぶつかい

せかいじゆう

せきしようも

せきじゆうじ

せきじようし

せしゆうしや

そうきよくし

そしきじよう

たいがくしや

たいきよくず

たいしゆうか

たいしゆうし

たいしようか

たいしようき

たいしよくか

たいじゆうさ

たいちようき

たぎようかい

たはいしよく

だいがくしや

だいしようじ

だいしようり

ちじようかい

ちじようしや

ちちゆうかい

ちめいしよう

ちやくしゆつ

ちゆうかくし

ちゆうかくは

ちゆうかくぶ

ちゆうきよう

ちゆうしつし

ちゆうしつゆ

ちゆうしやき

ちゆうしやく

ちようかいひ

ちようごうか

ちようしやく

ちようじゆう

ちようじゆか

ちようそくき

ちようばいか

ちりがくしや

ていがくしや

ていしゆうは

ていしようひ

ていしよくや

ていじゆうち

てきようしや

てないしよく

ときようそう

とけいしゆう

とけいしよう

とちゆうかい

どうしやくが

どうちゆうき

どちやくしゆ

ならいしよう

にじゆうだい

にゆうきよう

にゆうきよく

はじようしや

はれいしよう

ばいしようふ

ばいしようろ

ばたいじゆう

ばはいきよう

ひしようしつ

ひじようしき

ひたいしよう

ひだいしよう

ひやくしゆつ

びちゆうかく

ふかいしゆう

ふきようしや

ふくしゆうき

ふくじゆうき

ふしようしや

ふせいしよう

ふていしよう

ふていちよう

ふとうかいこ

ふはいしゆう

ふふくじゆう

ぶたいちよう

ぶちようかい

へいがくしや

ほうしやくじ

ほどうきよう

みかいしゆう

みちやくしゆ

みようじゆう

みようじゆつ

むきようしつ

むきようそう

むぎようしや

むさいしよく

むそうきよく

むばいしよう

めいしようち

めいしようぶ

めいちようし

やくじようび

やそうきよく

ゆうきようひ

らいちようか

りそうきよう

りゆうきよく

るけいしゆう

れきしようご

ろうきよくか

ろうきよくし

ろこうきよう

わいしようか

わかいしゆう

それぞれ、足りない文字を色々頑張って見つけると、案外あるので、6文字ではなく、7文字・8文字を探すことにしました。

高み

意気込んだは良いものの、7文字は一つも出てきませんでした。1単語の猶予を与えても出てこず...2単語の猶予を与えると、9個の単語が出てきました。

8文字に関しては5単語の猶予も見てみましたがなかなかありませんでした。

6文字は沢山あるので、7文字を協力プレイで探しました。

まとめ

6文字はめっちゃありますが、一応答として一例を。


あいしょうか 愛傷歌, 相性, 愛書, 哀史, 愛, 医師, 書, 衣装, 陽, 胃小窩

他の物もここらへんを中心に探してみればザクザク見つかると思います。

7文字に関しては、ありませんでした。頑張って探しましたがあの辞書と僕の協力プレイの限りは無いです。

惜しかったのとしては、



がいしょうしゃ
けいしょうしゃ
たいしょうしゃ
ていしょうしゃ
ないしょうしゃ
しゅうきょうし
じゅうきょうど
むしゅうきょう

でした。

特に上の方にある「〜いしょうしゃ」は「いしょうしゃ」だけが見つからないものが多くてとても惜しい!って感じですね。

楽しかったです。やはり計算機の力は凄いなぁ...(探索をしただけ

Notes

1 「ー」「ん」から始まる単語が無いので

2 計算量を考える前に決めたんです。Pythonでも良かったなぁ...

Read more?

3次方程式の判別式

黄茶の問題を解いていると判別式をよく使います。3次方程式に対しても使いたい場面がちょっとあったので、考えます。

Jan 19 2019

あけましておめでとうございます

アケオメ

Jan 07 2019

数学 I(三角法) を勉強していく上で思ったこととかメモ

Oct 11 2018

黄茶の旅日記の様なものです。数Iの三角法です。

画面指紋認証の仕組みって

Jun 11 2018

最近、画面指紋認証の記事を見かけまして、「そういやこれどうやって出来てるのかな...」と思って記事探してみてもなかったので(英語でも少なかった)、幾つかのページ(参考文献)から引っ張り出してきた情報を元に記事を書きます

Rustにおけるファイル分割

Rustは、モジュールシステムも色々決まりがあって整っているので、単にファイルを分けて書こうと思った場合にも、整った綺麗な書き方をするには難しい言語に感じます。自分も、丁度Rustでプログラムを書いていた時に迷って良いリポジトリから良い書き方を見つけたのでその紹介をしようと思います

Jul 19 2018

042933964230の暗号について調べてみた

Apr 23 2018

謎のサイトと言われて少し前に話題になったやつを調べてみました

日本一早いサイト選手権

阿部寛のホームページが爆速なのでそれよりはやいページ無いかなぁと適当に探してみた結果です。

Sep 22 2018

[円柱の体積文字列] 英単語をgrepできるサイトを作りました

Sep 17 2018

円の体積文字列で別の例を探すために英単語をgrep出来るサイトを作りました

数学 I(二次関数) を勉強していく上で思ったこととかメモ

黄茶の二次関数が終わったので、その学習中に思ったことを適当にメモしておきます

Sep 16 2018

IEは最高のブラウザ / IE is the best browser

Sep 16 2018

世間では何故かIEが蔑まれているようですが、そんなブラウザにも素晴らしいところが沢山あるのです

Explain Backpropagation Like I'm Five

Jul 13 2018

Recently, there are many successful news with the artificial intelligence (AI). Machine translation, object detection, automatic modeling, motion capture and so on... Even the optical illusion that only your brain should be able to perform has been achieved by the AI.

線の長さを積分で考えてみる

Sep 11 2018

今回は、前回積分を使って面積(小さな面積の集合)を求めたので、今回は線(小さな線の集合)の長さを求めていければ良いなぁみたいな感じでやっていけたらと思っています。

積分で原始関数の差を求めると元の函数の面積が出る理由

今回は積分の面白い性質である、原始関数の差が元の函数の面積となるという性質についてそうなる理由を気持ちだけでも書いていきます。

Sep 04 2018

「国語に関する世論調査」を読んで思ったこととか

Aug 28 2018

国の日本語に関する調査を見て最近の日本語の変化について知りました。

新しいブログシステムを構築したのでやったことを記録

前の古臭いブログシステムのままだと嫌だったので、新しいブログシステムを構築しました。

Aug 22 2018

共用サーバーで非同期通信チャットアプリを作る

今日は、さくらサーバーのライトプランという制限が多いサーバーでなんとか非同期通信を実現すべく奮闘したので、その記録をしたいと思います。

Aug 21 2018

前にブログに追加した機能

前にブログに追加した機能が使えるかどうかのテスト用.

Aug 21 2018

[素因数分解] Trial Division / 試し割り法

試し割り法は素因数分解の一番愚直なアルゴリズムです。この解説をします。

Aug 19 2018