ランダムに作成したテキストファイルに共通するパターンが複数存在する場合に何種類の文字から構成されていればパターンの数が安定するか

実際に行った事柄を最初に箇条書きでまとめておく。

・random moduleで使用する文字の種類(数)を限定した上で全体の文字数を揃えたファイルを複数作成

・作成したファイル中に同じパターンが2回以上出た場合にその数を数える

まず、ランダムな文字ファイルの作成プログラム。

#! /usr/bin/env python
# -*- coding:utf-8 -*-

import random

user_in = raw_input("What numbers do you like?: ")
text = ''
 
for i in range(int(user_in)):
     r = random.choice("ABCDEFGHI")
     text += str(r)
f = open("text_" + str(user_in) + ".txt", "w")
f.write(text)
f.close()

choiceメソッドで取得しているアルファベット数を変更する(ユーザーの入力で文字の種類を変更するようにすればよかった)。 今回は文字の種類の数を5, 6, 7, 8, 9, 10, 15, 20として8ファイル作成した。

次に作成したファイルに対して2回以上ヒットするパターンの検出プログラム。

#! /usr/bin/env python
# -*- coding:utf-8 -*-

import sys

temp = ''
filename = sys.argv[1]
inputfile = open(filename, 'r')

user_in_min = raw_input("min text length: ")
user_in_max = raw_input("max text length: ")

text_list = {}
result = ''
count = 0

for line in inputfile:
    temp = line.rstrip()
    for k in range(int(user_in_min), int(user_in_max) + 1):
        for i in range(len(temp)):
            if (int(i) + int(k)) <= len(temp):
                if text_list.has_key(temp[i:i+k+1]):
                    text_list[temp[i:i+k+1]] += 1
                else:
                    text_list[temp[i:i+k+1]] = 1

for u in sorted(text_list.keys(), key = lambda x: len(x)):
    if int(text_list[u]) >= 2:
        count += 1
        result += str(u) + "\t" + str(text_list[u]) + "\n"
result += str(count) + "\n"
inputfile.close()
name = str(filename).split(".txt")[0]
f = open(str(name) + "_result.txt", "w")
f.write(result)
f.close()

パターンの長さはユーザー指定ではあるが今回全て5〜20の範囲で探した。

(user_in_min = 5, usr_in_max = 20)

結果として、

文字の種類：2回以上ヒットしたパターンの数
5：72
6：35
7：18
8：23
9：16
10：15
15：15
20：15

パターンマッチのプログラムを見ればわかるが重複を許しているので 短いマッチは長いものに含まれていることが考えられるため 重複を許容しなければもっと数が減って文字の種類がもう少し少ない段階から 2回以上ヒットするパターンの数が一定になるかもしれない。 文字の総数とパターンの長さを変更してもう少し細かく見れば 何かよくわからないが見えるかも...しれない......。