ウェブページの中の回文検出をやってみる in Python

https://qiita.com/khsk/items/22292a9a38f187fd3378 をみてやりたくなったのでやります。

回文かどうか判定する関数を作ってみる

回文かどうかの判断は簡単で$n$文字の文章が存在するとき、$x$の床関数を$\lfloor x \rfloor$ 、$a$番目の文字を$s(a)$と表すと、整数の集合を$N$とすると、すべての$i\in N < \lfloor \frac{n}{2} \rfloor$に対して$s(i) = s(n-i)$が成り立つことから判断できます。
pythonで回文判断の関数を作ってみると

def is_kaibun(kaibun):
    for i in range(len(kaibun)//2):
        if kaibun[i] != kaibun[-i-1]:
            return False
    return True

となります。
ここでkaibunが回文かどうか判断したい文で、返り値は結果のbooleanになります。

回文を探す関数を作ってみる

回文を探してprintする関数を考えてみます、まずは力技でやってみましょう。
回文は必ず最初の文字と最後の文字は一致していなければなりません、なので回文かどうか判断すべき文章は最初の文字と最後の文字は一致している部分のみとなります。
あとは力技でやる場合、脳死でぐるぐる回せば良いので

def search_kaibun(sentence):
    for i in range(len(sentence)-1):
        for j in range(i+1,len(sentence)):
            if sentence[i] != sentence[j]:
                if is_kaibun(sentence[i:j+1]):
                    print(sentence[i:j+1])

となります、楽ですね。

ここまでのコードを動かしてみましょう

def is_kaibun(string):
    for i in range(int(len(string)/2)):
        if string[i] != string[-i-1]:
            return False
    return True

def search_kaibun(sentence):
    for i in range(len(sentence)-1):
        for j in range(i+1,len(sentence)):
            if sentence[i] == sentence[j]:
                if is_kaibun(sentence[i:j+1]):
                    print(sentence[i:j+1])

search_kaibun("これはテストです。たけやぶやけた")

を実行してみると

たけやぶやけた
けやぶやけ
やぶや

となり無事回文を取得できていることがわかります。

ウェブページの情報を取得する

次はスクレイピングの部分を作成してみましょう。今回はurllibとBeautifulSoup,sslを使用します。
あるウェブページのhtmlを取得するコードは、

import ssl
import urllib
from bs4 import BeautifulSoup

ssl._create_default_https_context = ssl._create_unverified_context
html = urllib.request.urlopen(url).read()
bs_obj = BeautifulSoup(html, "lxml")

ここでurlはウェブページのurlです。
これでbs_objにはウェブページのhtmlの情報が格納されました。しかしほしいのはウェブページの本文です。そこでhttps://python.g.hatena.ne.jp/y_yanbe/20081025/1224910392 を参考に(というかコピーして)次のような関数を作ります。

from bs4 import BeautifulSoup, NavigableString, Declaration, Comment

def get_navigable_strings(soup):
    if isinstance(soup, NavigableString):
        if type(soup) not in (Comment, Declaration) and soup.strip():
            yield soup
    elif soup.name not in ('script', 'style'):
        for c in soup.contents:
            for g in get_navigable_strings(c):
                yield g

この関数を使用して上のウェブページのhtmlのデータを取得するコードは

from bs4 import BeautifulSoup, NavigableString, Declaration, Comment

def get_navigable_strings(soup):
    if isinstance(soup, NavigableString):
        if type(soup) not in (Comment, Declaration) and soup.strip():
            yield soup
    elif soup.name not in ('script', 'style'):
        for c in soup.contents:
            for g in get_navigable_strings(c):
                yield g

ssl._create_default_https_context = ssl._create_unverified_context
html = urllib.request.urlopen(url).read()
bs_obj = BeautifulSoup(html, "lxml")
text = "".join(get_navigable_strings(bs_obj)).replace("、","").replace(" ","").replace("　","")

となります。ここで最後のreplaceは空白や"、"を削除するためのものです。
一応関数化しておきましょう

def search_kaibun_in_url(url):
    html = urllib.request.urlopen(url).read()
    bs_obj = BeautifulSoup(html, "lxml")
    text = "".join(get_navigable_strings(bs_obj))

ウェブページの中の回文を出力する

ここまで来たら後はこれらのコードを組み合わせるだけです。

import ssl
import urllib
import MeCab
from bs4 import BeautifulSoup, NavigableString, Declaration, Comment

def is_kaibun(string):
    for i in range(int(len(string)/2)):
        if string[i] != string[-i-1]:
            return False
    return True

def search_kaibun(sentence):
    for i in range(len(sentence)-1):
        for j in range(i+1,len(sentence)):
            if sentence[i] == sentence[j]:
                if is_kaibun(sentence[i:j+1]):
                    print(sentence[i:j+1])

def get_navigable_strings(soup):
    if isinstance(soup, NavigableString):
        if type(soup) not in (Comment, Declaration) and soup.strip():
            yield soup
    elif soup.name not in ('script', 'style'):
        for c in soup.contents:
            for g in get_navigable_strings(c):
                yield g

def search_kaibun_in_url(url):
    html = urllib.request.urlopen(url).read()
    bs_obj = BeautifulSoup(html, "lxml")
    text = "".join(get_navigable_strings(bs_obj))
    search_kaibun(text)

wikipediaの回文のページ(https://ja.wikipedia.org/wiki/%E5%9B%9E%E6%96%87 )をもとに実行してみると

 - 
iki
iki
通常通
2.2
ーナー
3.3
の街の
ene
ada
文の文
のもの
五七五
七五七
七七
はらは
ついにいつ
いにい
nn
五・七・五
・七・
そもそ
もそも
りあり
かさか
aka
akasaka
kasak
asa
aka
11
1661
66
00
000
00
.S.
タッタ
て出て
の後の
わかみかものとかなかとのもかみかわ
かみか
かみかものとかなかとのもかみか
みかものとかなかとのもかみ
かものとかなかとのもか
ものとかなかとのも
のとかなかとの
とかなかと
︙ 
aa
ара
ata
aza
λλ
ara
երե
aBa
aha
asa
ede
nyn
cc
ugu
сс
संस
 / 
 / 
11
1月1
oo

と一応それっぽいものが取得できました。
しかしこれで良いのでしょうか？
このプログラムだと「竹藪焼けた」という漢字の入った回文を取得できません。
どのようにしたら漢字の入った漢文を見つけることができるでしょうか。

ふりがなを作成する

漢字の入った回文を取得するためふりがなを作成する関数を作成します。
MeCabでは文章を入力すると単語を返してくれますが、このとき以下のように単語と一緒に単語の読みを返してくれます。

吾輩  名詞,代名詞,一般,*,*,*,吾輩,ワガハイ,ワガハイ
は 助詞,係助詞,*,*,*,*,は,ハ,ワ
猫 名詞,一般,*,*,*,*,猫,ネコ,ネコ
で 助動詞,*,*,*,特殊・ダ,連用形,だ,デ,デ
ある  助動詞,*,*,*,五段・ラ行アル,基本形,ある,アル,アル
EOS

これの最後２つを利用できそうです。今回は「は」を「わ」とは読まず「は」として取り扱うようにしましょう。
MeCabをpythonから呼んで、解析するコードは

import MeCab

in_text = "吾輩は猫である"
mecab = MeCab.Tagger()
print(mecab.parse(in_text))

です。
読み方だけを取得するには

import MeCab

in_text = "吾輩は猫である"
mecab = MeCab.Tagger()
text = [parsed_sentence.split(",")[-2] for parsed_sentence in mecab.parse(in_text).split("\n")[:-2]]
kaibun = "".join(text)
print(kaibun)

となります。
ではこれを利用して回文を検出するコードを作成しましょう。
MeCabで取得できる読み方はすべてカタカナで表記されています、なのでis_kaibun関数の引数に作成した読み方を与えると漢字でも判断できそうです。
なのでsearch_kaibun関数を次のように修正してみます。

def search_kaibun(sentence):
    mecab = MeCab.Tagger()
    for i in range(len(sentence)-1):
        for j in range(i+1,len(sentence)):
            text = [parsed_sentence.split(",")[-2] for parsed_sentence in mecab.parse(sentence[i:j+1]).split("\n")[:-2]]
            kaibun = "".join(text)
            if kaibun[0] == kaibun[-1]:
                if is_kaibun(kaibun):
                    print(kaibun, sentence[i:j+1])

ではこの関数を用いて漢字の入った回文の検出をwikipediaの回文のページで行ってみます。

* ht
* htm
* html
* tm
* tml
* ml
*  -
*  - 
**  - W
**  - Wi
**  - Wik
**  - Wiki
**  - Wikip
**  - Wikipe
**  - Wikiped
**  - Wikipedi
**  - Wikipedia
︙

まず分かることは"*"が入って本来回文でないものも回文と認識されることがわかります。
次にとても遅いということです。文章をいちいちMeCabを動かして作成しているからだと思われます。
実際MeCabにwikipediaの回文のページ全文を入れてみると、すぐ結果が出ることがわかります。
これをマシにしてみましょう。

単語ベースの回文検出にする

今まで文字ベースで回文検出を行っていました。しかし文字ベースだと計算量がとても大きくなることがわかります。
なので、単語ベースの回文検出をやってみましょう。
単語ベースの回文検出を行う場合、必要なものは単語、単語の読み、単語のタイプです。
単語のタイプが必要な理由は例えば回文中に"("などは入ってほしくないためです。
まず単語、単語の読み、単語のタイプを取得するコードを書きます。

parsed_text = mecab.parse(text).split("\n")[:-2]
word = [ps.split(",")[-2] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
surface = [ps.split(",")[0].split("\t")[0] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
word_type = [ps.split(",")[0].split("\t")[1] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]

…汚いコードですが目を瞑って先に進みましょう。これでwordに読み、surfaceに単語、word_typeに単語のタイプが入ります。
これからsearch_kaibun_in_url関数は

def search_kaibun_in_url(url):
    html = urllib.request.urlopen(url).read()
    bs_obj = BeautifulSoup(html, "lxml")
    text = "".join(get_navigable_strings(bs_obj))
    mecab = MeCab.Tagger()
    parsed_text = mecab.parse(text).split("\n")[:-2]
    word = [ps.split(",")[-2] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
    surface = [ps.split(",")[0].split("\t")[0] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
    word_type = [ps.split(",")[0].split("\t")[1] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
    search_kaibun(word, surface, word_type)

と書き換えられます。

これらをもとにsearch_kaibun関数を書き換えてみましょう。
書き換えたsearch_kaibun関数はまず読みの中に"*"が入っていてはいけません、またタイプが記号の単語も文章中に入らない様にしなければなりません。
その様にsearch_kaibun関数を書き換えると次のようになることがわかります。

def search_kaibun(word, surface, word_type):
    mecab = MeCab.Tagger()
    for i in range(len(word)-1):
        for j in range(i+1,len(word)):
            kaibun = "".join(word[i:j+1])
            if not "*" in kaibun and not "記号" in word_type[i:j+1] and is_kaibun(kaibun):
                print(kaibun, ":", "".join(surface[i:j+1]))                    

これをもとに動かしてみると

ミガカヌカガミ : 磨かぬ鏡
タケヤブヤケタ : 竹藪焼けた
ノモノ : のもの
ゴナナゴ : 五七五
ナナゴナナ : 七五七
ナナナナ : 七七
ハラハ : はらは
トモツイニイツモト : ともついにいつもと
モツイニイツモ : もついにいつも
ハルハ : 春は
トモツイニイツモト : ともついにいつもと
ゴ・ナナ・ゴ : 五・七・五
・ナナ・ : ・七・
モノモ : 者も
テデテ : て出て
ワカミカモノトカナカトノモカミカワ : わかみかものとかなかとのもかみかわ
ミカモノトカナカトノモカミ : みかものとかなかとのもかみ
モノトカナカトノモ : ものとかなかとのも
トカナカト : とかなかと
カミカ : かみか
タイモクヨトントコトントヨクモイタ : たいもくよとんとことんとよくもいた
モクヨトントコトントヨクモ : もくよとんとことんとよくも
トントコトント : とんとことんと
ントコトン : んとことん
ナカシミシカシシカシミシカナ : なかしみしかししかしみしかな
シミシ : しみし
シミシカシシカシミシ : しみしかししかしみし
︙

となりました。"磨かぬ鏡"や"竹藪焼けた"の様に漢字が入った回文も取得できています。
しかし、"わかみかものとかなかとのもかみかわ"、"みかものとかなかとのもかみ"、"ものとかなかとのも"の様に対称であるという回文の性質上、回文の中身も回文となるのでそれを取得してしまっています。
次はこれらを弾いてみましょう。

最長の回文のみを取り出す

おそらく、ほしい回文はある部分において最長の回文だと思われます。この回文はある回文の部分要素になっていないはずです。
そこで最長の回文のみを取り出すため、最長の回文を検出したらその分検出をスキップするようにしましょう
最長の回文は性質上、その回文に含まれる回分より長いはずです。なのでsearch_kaibun関数を次のように書き換えます

def search_kaibun(word, surface, word_type):
    skip = 0
    for i in range(len(word)-1):
        if skip > 0:
            skip-=1
        else:
            longer_kaibun = ""
            for j in range(i+1,len(word)):
                kaibun = "".join(word[i:j+1])
                if not "*" in kaibun and not "記号" in word_type[i:j+1] and is_kaibun(kaibun):
                    #print(kaibun, ":", "".join(word[i:j+1]))
                    longer_kaibun = surface[i:j+1]
            else:
                if longer_kaibun != "":
                    skip = len(longer_kaibun)-1
                    print("".join(longer_kaibun))

記号が先頭にくる回文は存在しないため、記号が先頭に来た場合もスキップするようにしましょう。

def search_kaibun(word, surface, word_type):
    skip = 0
    for i in range(len(word)-1):
        if word_type[i] == "記号":
            pass
        elif skip > 0:
            skip-=1
        else:
            longer_kaibun = ""
            for j in range(i+1,len(word)):
                kaibun = "".join(word[i:j+1])
                if not "*" in kaibun and not "記号" in word_type[i:j+1] and is_kaibun(kaibun):
                    #print(kaibun, ":", "".join(word[i:j+1]))
                    longer_kaibun = surface[i:j+1]
            else:
                if longer_kaibun != "":
                    skip = len(longer_kaibun)-1
                    print("".join(longer_kaibun))

これで最長の回文が取得できるはずです。またwikipediaの回文のページで動かしてみましょう。
すると結果は

磨かぬ鏡
竹藪焼けた
のもの
五七五
七七
はらは
ともついにいつもと
春は
ともついにいつもと
五・七・五
者も
て出て
わかみかものとかなかとのもかみかわ
たいもくよとんとことんとよくもいた
なかしみしかししかしみしかな
みなくさのなははくとしれくすりなりすくれしとくははなのさくなみ
たのむそのいかにもにかいのそむのた
さかのなはやとりたりとやはなのかさ
はかなの世しばしよしばし世の中は
はかなのよしはしよしはしよのなかは
にわのわに
まさかさかさま
またたび浴びたタマ
ダンスがすんだ
文全部
さかさ
せとちとせ
まさかサカサマ
野茂のものは野茂のもの
渋い武士
しぶいぶし
なな
た歌
こたつたこ
だんしがしんだ

うまく回文が取れました。

コード全体

import ssl
import urllib
import MeCab
from bs4 import BeautifulSoup, NavigableString, Declaration, Comment

def is_kaibun(string):
    for i in range(int(len(string)/2)):
        if string[i] != string[-i-1]:
            return False
    return True

def search_kaibun(word, surface, word_type):
    skip = 0
    for i in range(len(word)-1):
        if word_type[i] == "記号":
            pass
        elif skip > 0:
            skip-=1
        else:
            longer_kaibun = ""
            for j in range(i+1,len(word)):
                kaibun = "".join(word[i:j+1])
                if not "*" in kaibun and not "記号" in word_type[i:j+1] and is_kaibun(kaibun):
                    longer_kaibun = surface[i:j+1]
            else:
                if longer_kaibun != "":
                    skip = len(longer_kaibun)-1
                    print("".join(longer_kaibun))

def get_navigable_strings(soup):
    if isinstance(soup, NavigableString):
        if type(soup) not in (Comment, Declaration) and soup.strip():
            yield soup
    elif soup.name not in ('script', 'style'):
        for c in soup.contents:
            for g in get_navigable_strings(c):
                yield g

def search_kaibun_in_url(url):
    html = urllib.request.urlopen(url).read()
    bs_obj = BeautifulSoup(html, "lxml")
    text = "".join(get_navigable_strings(bs_obj))
    mecab = MeCab.Tagger()
    parsed_text = mecab.parse(text).split("\n")[:-2]
    word = [ps.split(",")[-2] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
    surface = [ps.split(",")[0].split("\t")[0] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
    word_type = [ps.split(",")[0].split("\t")[1] for ps in parsed_text if len(ps.split(",")[0].split("\t")) > 1]
    search_kaibun(word, surface, word_type)

search_kaibun_in_url("https://ja.wikipedia.org/wiki/%E5%9B%9E%E6%96%87")

まとめ

ピアスとタバコが似合う女の子をすこれ

参考ページ

https://qiita.com/khsk/items/22292a9a38f187fd3378
https://python.g.hatena.ne.jp/y_yanbe/20081025/1224910392
https://qiita.com/KogeTakahiro/items/8bd05d937f2be13039cb