文字列のパターンを抽出する方法

ランダムに生成された文字列からパターンを抽出してグループ化したいのですが、どのようにプログラムを組んだら良いのでしょうか。

lang
1あいうえおかきくけこあいうえおかき
2あいうえおあいうえお

上記の文字列を例に話します。
「あいうえお」というパターンで4回出てきているのでこれをグループ化。
「あいうえおかき」も2回出てきていますが、「あいうえお」はすでにグループ化されてるので「かき」という部分だけだけをグループ化。

という風にしたいのですが、みなさんはどのようなアルゴリズムを思いつきますか?
全くやり方が思い浮かばないので、非効率な処理になっても構いません。
お知恵をお貸しください。
言語はなんで良いです。

行動規範の内容に同意します

回答2件

まず全てのパターンをチェックする所からですね。
その後、何文字以上をやるのか等を決めないと、論理的にルールが策定できません。
アルゴリズムを説明するのは苦手なので、Javascriptでざっくり書いてみました。

lang
1var inputText = 'あいうえおかきくけこあいうえおかきあいうえおあいうえお';
2var result = {};
3
4for(var start=0; start<inputText.length; start++){
5for(var length=(inputText.length - start); length>0; length--){
6	var slicedText = inputText.slice(start, length + start);
7	if(slicedText == ''){
8		break;
9	}
10	if(result[slicedText] === undefined){
11		result[slicedText] = 1;
12	} else {
13		result[slicedText]++;
14	}
15}
16}
17// 結果
18console.log(JSON.stringify(result));

結果は以下のように出ます。
この結果から、抽出したいものを取得する様にすれば良いかと思います。
如何でしょうか？

lang
1{
2    "あ": 4, 
3    "あい": 4, 
4    "あいう": 4, 
5    "あいうえ": 4, 
6    "あいうえお": 4, 
7    "あいうえおあ": 1, 
8    "あいうえおあい": 1, 
9    "あいうえおあいう": 1, 
10    "あいうえおあいうえ": 1, 
11    "あいうえおあいうえお": 1, 
12    "あいうえおか": 2, 
13    "あいうえおかき": 2, 
14    "あいうえおかきあ": 1, 
15    "あいうえおかきあい": 1, 
16    "あいうえおかきあいう": 1, 
17    "あいうえおかきあいうえ": 1, 
18    "あいうえおかきあいうえお": 1, 
19    "あいうえおかきあいうえおあ": 1, 
20    "あいうえおかきあいうえおあい": 1, 
21    "あいうえおかきあいうえおあいう": 1, 
22    "あいうえおかきあいうえおあいうえ": 1, 
23    "あいうえおかきあいうえおあいうえお": 1, 
24    "あいうえおかきく": 1, 
25    "あいうえおかきくけ": 1, 
26    "あいうえおかきくけこ": 1, 
27    "あいうえおかきくけこあ": 1, 
28    "あいうえおかきくけこあい": 1, 
29    "あいうえおかきくけこあいう": 1, 
30    "あいうえおかきくけこあいうえ": 1, 
31    "あいうえおかきくけこあいうえお": 1, 
32    "あいうえおかきくけこあいうえおか": 1, 
33    "あいうえおかきくけこあいうえおかき": 1, 
34    "あいうえおかきくけこあいうえおかきあ": 1, 
35    "あいうえおかきくけこあいうえおかきあい": 1, 
36    "あいうえおかきくけこあいうえおかきあいう": 1, 
37    "あいうえおかきくけこあいうえおかきあいうえ": 1, 
38    "あいうえおかきくけこあいうえおかきあいうえお": 1, 
39    "あいうえおかきくけこあいうえおかきあいうえおあ": 1, 
40    "あいうえおかきくけこあいうえおかきあいうえおあい": 1, 
41    "あいうえおかきくけこあいうえおかきあいうえおあいう": 1, 
42    "あいうえおかきくけこあいうえおかきあいうえおあいうえ": 1, 
43    "あいうえおかきくけこあいうえおかきあいうえおあいうえお": 1, 
44    "い": 4, 
45    "いう": 4, 
46    "いうえ": 4, 
47    "いうえお": 4, 
48    "いうえおあ": 1, 
49    "いうえおあい": 1, 
50    "いうえおあいう": 1, 
51    "いうえおあいうえ": 1, 
52    "いうえおあいうえお": 1, 
53    "いうえおか": 2, 
54    "いうえおかき": 2, 
55    "いうえおかきあ": 1, 
56    "いうえおかきあい": 1, 
57    "いうえおかきあいう": 1, 
58    "いうえおかきあいうえ": 1, 
59    "いうえおかきあいうえお": 1, 
60    "いうえおかきあいうえおあ": 1, 
61    "いうえおかきあいうえおあい": 1, 
62    "いうえおかきあいうえおあいう": 1, 
63    "いうえおかきあいうえおあいうえ": 1, 
64    "いうえおかきあいうえおあいうえお": 1, 
65    "いうえおかきく": 1, 
66    "いうえおかきくけ": 1, 
67    "いうえおかきくけこ": 1, 
68    "いうえおかきくけこあ": 1, 
69    "いうえおかきくけこあい": 1, 
70    "いうえおかきくけこあいう": 1, 
71    "いうえおかきくけこあいうえ": 1, 
72    "いうえおかきくけこあいうえお": 1, 
73    "いうえおかきくけこあいうえおか": 1, 
74    "いうえおかきくけこあいうえおかき": 1, 
75    "いうえおかきくけこあいうえおかきあ": 1, 
76    "いうえおかきくけこあいうえおかきあい": 1, 
77    "いうえおかきくけこあいうえおかきあいう": 1, 
78    "いうえおかきくけこあいうえおかきあいうえ": 1, 
79    "いうえおかきくけこあいうえおかきあいうえお": 1, 
80    "いうえおかきくけこあいうえおかきあいうえおあ": 1, 
81    "いうえおかきくけこあいうえおかきあいうえおあい": 1, 
82    "いうえおかきくけこあいうえおかきあいうえおあいう": 1, 
83    "いうえおかきくけこあいうえおかきあいうえおあいうえ": 1, 
84    "いうえおかきくけこあいうえおかきあいうえおあいうえお": 1, 
85    "う": 4, 
86    "うえ": 4, 
87    "うえお": 4, 
88    "うえおあ": 1, 
89    "うえおあい": 1, 
90    "うえおあいう": 1, 
91    "うえおあいうえ": 1, 
92    "うえおあいうえお": 1, 
93    "うえおか": 2, 
94    "うえおかき": 2, 
95    "うえおかきあ": 1, 
96    "うえおかきあい": 1, 
97    "うえおかきあいう": 1, 
98    "うえおかきあいうえ": 1, 
99    "うえおかきあいうえお": 1, 
100    "うえおかきあいうえおあ": 1, 
101    "うえおかきあいうえおあい": 1, 
102    "うえおかきあいうえおあいう": 1, 
103    "うえおかきあいうえおあいうえ": 1, 
104    "うえおかきあいうえおあいうえお": 1, 
105    "うえおかきく": 1, 
106    "うえおかきくけ": 1, 
107    "うえおかきくけこ": 1, 
108    "うえおかきくけこあ": 1, 
109    "うえおかきくけこあい": 1, 
110    "うえおかきくけこあいう": 1, 
111    "うえおかきくけこあいうえ": 1, 
112    "うえおかきくけこあいうえお": 1, 
113    "うえおかきくけこあいうえおか": 1, 
114    "うえおかきくけこあいうえおかき": 1, 
115    "うえおかきくけこあいうえおかきあ": 1, 
116    "うえおかきくけこあいうえおかきあい": 1, 
117    "うえおかきくけこあいうえおかきあいう": 1, 
118    "うえおかきくけこあいうえおかきあいうえ": 1, 
119    "うえおかきくけこあいうえおかきあいうえお": 1, 
120    "うえおかきくけこあいうえおかきあいうえおあ": 1, 
121    "うえおかきくけこあいうえおかきあいうえおあい": 1, 
122    "うえおかきくけこあいうえおかきあいうえおあいう": 1, 
123    "うえおかきくけこあいうえおかきあいうえおあいうえ": 1, 
124    "うえおかきくけこあいうえおかきあいうえおあいうえお": 1, 
125    "え": 4, 
126    "えお": 4, 
127    "えおあ": 1, 
128    "えおあい": 1, 
129    "えおあいう": 1, 
130    "えおあいうえ": 1, 
131    "えおあいうえお": 1, 
132    "えおか": 2, 
133    "えおかき": 2, 
134    "えおかきあ": 1, 
135    "えおかきあい": 1, 
136    "えおかきあいう": 1, 
137    "えおかきあいうえ": 1, 
138    "えおかきあいうえお": 1, 
139    "えおかきあいうえおあ": 1, 
140    "えおかきあいうえおあい": 1, 
141    "えおかきあいうえおあいう": 1, 
142    "えおかきあいうえおあいうえ": 1, 
143    "えおかきあいうえおあいうえお": 1, 
144    "えおかきく": 1, 
145    "えおかきくけ": 1, 
146    "えおかきくけこ": 1, 
147    "えおかきくけこあ": 1, 
148    "えおかきくけこあい": 1, 
149    "えおかきくけこあいう": 1, 
150    "えおかきくけこあいうえ": 1, 
151    "えおかきくけこあいうえお": 1, 
152    "えおかきくけこあいうえおか": 1, 
153    "えおかきくけこあいうえおかき": 1, 
154    "えおかきくけこあいうえおかきあ": 1, 
155    "えおかきくけこあいうえおかきあい": 1, 
156    "えおかきくけこあいうえおかきあいう": 1, 
157    "えおかきくけこあいうえおかきあいうえ": 1, 
158    "えおかきくけこあいうえおかきあいうえお": 1, 
159    "えおかきくけこあいうえおかきあいうえおあ": 1, 
160    "えおかきくけこあいうえおかきあいうえおあい": 1, 
161    "えおかきくけこあいうえおかきあいうえおあいう": 1, 
162    "えおかきくけこあいうえおかきあいうえおあいうえ": 1, 
163    "えおかきくけこあいうえおかきあいうえおあいうえお": 1, 
164    "お": 4, 
165    "おあ": 1, 
166    "おあい": 1, 
167    "おあいう": 1, 
168    "おあいうえ": 1, 
169    "おあいうえお": 1, 
170    "おか": 2, 
171    "おかき": 2, 
172    "おかきあ": 1, 
173    "おかきあい": 1, 
174    "おかきあいう": 1, 
175    "おかきあいうえ": 1, 
176    "おかきあいうえお": 1, 
177    "おかきあいうえおあ": 1, 
178    "おかきあいうえおあい": 1, 
179    "おかきあいうえおあいう": 1, 
180    "おかきあいうえおあいうえ": 1, 
181    "おかきあいうえおあいうえお": 1, 
182    "おかきく": 1, 
183    "おかきくけ": 1, 
184    "おかきくけこ": 1, 
185    "おかきくけこあ": 1, 
186    "おかきくけこあい": 1, 
187    "おかきくけこあいう": 1, 
188    "おかきくけこあいうえ": 1, 
189    "おかきくけこあいうえお": 1, 
190    "おかきくけこあいうえおか": 1, 
191    "おかきくけこあいうえおかき": 1, 
192    "おかきくけこあいうえおかきあ": 1, 
193    "おかきくけこあいうえおかきあい": 1, 
194    "おかきくけこあいうえおかきあいう": 1, 
195    "おかきくけこあいうえおかきあいうえ": 1, 
196    "おかきくけこあいうえおかきあいうえお": 1, 
197    "おかきくけこあいうえおかきあいうえおあ": 1, 
198    "おかきくけこあいうえおかきあいうえおあい": 1, 
199    "おかきくけこあいうえおかきあいうえおあいう": 1, 
200    "おかきくけこあいうえおかきあいうえおあいうえ": 1, 
201    "おかきくけこあいうえおかきあいうえおあいうえお": 1, 
202    "か": 2, 
203    "かき": 2, 
204    "かきあ": 1, 
205    "かきあい": 1, 
206    "かきあいう": 1, 
207    "かきあいうえ": 1, 
208    "かきあいうえお": 1, 
209    "かきあいうえおあ": 1, 
210    "かきあいうえおあい": 1, 
211    "かきあいうえおあいう": 1, 
212    "かきあいうえおあいうえ": 1, 
213    "かきあいうえおあいうえお": 1, 
214    "かきく": 1, 
215    "かきくけ": 1, 
216    "かきくけこ": 1, 
217    "かきくけこあ": 1, 
218    "かきくけこあい": 1, 
219    "かきくけこあいう": 1, 
220    "かきくけこあいうえ": 1, 
221    "かきくけこあいうえお": 1, 
222    "かきくけこあいうえおか": 1, 
223    "かきくけこあいうえおかき": 1, 
224    "かきくけこあいうえおかきあ": 1, 
225    "かきくけこあいうえおかきあい": 1, 
226    "かきくけこあいうえおかきあいう": 1, 
227    "かきくけこあいうえおかきあいうえ": 1, 
228    "かきくけこあいうえおかきあいうえお": 1, 
229    "かきくけこあいうえおかきあいうえおあ": 1, 
230    "かきくけこあいうえおかきあいうえおあい": 1, 
231    "かきくけこあいうえおかきあいうえおあいう": 1, 
232    "かきくけこあいうえおかきあいうえおあいうえ": 1, 
233    "かきくけこあいうえおかきあいうえおあいうえお": 1, 
234    "き": 2, 
235    "きあ": 1, 
236    "きあい": 1, 
237    "きあいう": 1, 
238    "きあいうえ": 1, 
239    "きあいうえお": 1, 
240    "きあいうえおあ": 1, 
241    "きあいうえおあい": 1, 
242    "きあいうえおあいう": 1, 
243    "きあいうえおあいうえ": 1, 
244    "きあいうえおあいうえお": 1, 
245    "きく": 1, 
246    "きくけ": 1, 
247    "きくけこ": 1, 
248    "きくけこあ": 1, 
249    "きくけこあい": 1, 
250    "きくけこあいう": 1, 
251    "きくけこあいうえ": 1, 
252    "きくけこあいうえお": 1, 
253    "きくけこあいうえおか": 1, 
254    "きくけこあいうえおかき": 1, 
255    "きくけこあいうえおかきあ": 1, 
256    "きくけこあいうえおかきあい": 1, 
257    "きくけこあいうえおかきあいう": 1, 
258    "きくけこあいうえおかきあいうえ": 1, 
259    "きくけこあいうえおかきあいうえお": 1, 
260    "きくけこあいうえおかきあいうえおあ": 1, 
261    "きくけこあいうえおかきあいうえおあい": 1, 
262    "きくけこあいうえおかきあいうえおあいう": 1, 
263    "きくけこあいうえおかきあいうえおあいうえ": 1, 
264    "きくけこあいうえおかきあいうえおあいうえお": 1, 
265    "く": 1, 
266    "くけ": 1, 
267    "くけこ": 1, 
268    "くけこあ": 1, 
269    "くけこあい": 1, 
270    "くけこあいう": 1, 
271    "くけこあいうえ": 1, 
272    "くけこあいうえお": 1, 
273    "くけこあいうえおか": 1, 
274    "くけこあいうえおかき": 1, 
275    "くけこあいうえおかきあ": 1, 
276    "くけこあいうえおかきあい": 1, 
277    "くけこあいうえおかきあいう": 1, 
278    "くけこあいうえおかきあいうえ": 1, 
279    "くけこあいうえおかきあいうえお": 1, 
280    "くけこあいうえおかきあいうえおあ": 1, 
281    "くけこあいうえおかきあいうえおあい": 1, 
282    "くけこあいうえおかきあいうえおあいう": 1, 
283    "くけこあいうえおかきあいうえおあいうえ": 1, 
284    "くけこあいうえおかきあいうえおあいうえお": 1, 
285    "け": 1, 
286    "けこ": 1, 
287    "けこあ": 1, 
288    "けこあい": 1, 
289    "けこあいう": 1, 
290    "けこあいうえ": 1, 
291    "けこあいうえお": 1, 
292    "けこあいうえおか": 1, 
293    "けこあいうえおかき": 1, 
294    "けこあいうえおかきあ": 1, 
295    "けこあいうえおかきあい": 1, 
296    "けこあいうえおかきあいう": 1, 
297    "けこあいうえおかきあいうえ": 1, 
298    "けこあいうえおかきあいうえお": 1, 
299    "けこあいうえおかきあいうえおあ": 1, 
300    "けこあいうえおかきあいうえおあい": 1, 
301    "けこあいうえおかきあいうえおあいう": 1, 
302    "けこあいうえおかきあいうえおあいうえ": 1, 
303    "けこあいうえおかきあいうえおあいうえお": 1, 
304    "こ": 1, 
305    "こあ": 1, 
306    "こあい": 1, 
307    "こあいう": 1, 
308    "こあいうえ": 1, 
309    "こあいうえお": 1, 
310    "こあいうえおか": 1, 
311    "こあいうえおかき": 1, 
312    "こあいうえおかきあ": 1, 
313    "こあいうえおかきあい": 1, 
314    "こあいうえおかきあいう": 1, 
315    "こあいうえおかきあいうえ": 1, 
316    "こあいうえおかきあいうえお": 1, 
317    "こあいうえおかきあいうえおあ": 1, 
318    "こあいうえおかきあいうえおあい": 1, 
319    "こあいうえおかきあいうえおあいう": 1, 
320    "こあいうえおかきあいうえおあいうえ": 1, 
321    "こあいうえおかきあいうえおあいうえお": 1
322}

投稿2014/11/25 10:22

utun

総合スコア384

書いているうちにだいぶごちゃごちゃしてしまったので適当に脳内補完してください。

先頭の字を検索文字列に読み込む
検索文字が自身以外に対象文字列中に存在することを確認

3-1. 存在する場合
3-1-2. 対象文字列中の次の文字を検索文字列の末尾に追記し、自身以外に対象文字列中に存在することを確認
3-1-3. 対象文字列中に検索文字列が存在しなくなるまで3-1-1.を繰り返す
3-1-4. 対象文字列中に検索文字列が存在しなくなったら、最後の一文字を読み込む前の検索文字列をグループとする
3-1-5. グループとした文字列を対象文字列中から削除し、1.に戻る
3-2. 存在しない場合
3-2-1. 次の文字を読み込み、2. に戻る

lang
1あいうえおかきくけこあいうえおかき
2あいうえおあいうえお

上記の文字列に当てはめると
0. 「あ」を読み込み、対象文字列に「あ」が存在することを確認する。
0. 「あい」を読み込み、対象文字列に「あい」が存在することを確認する。
0. 上記を繰り返し、「あいうえお」を読み込み、対象文字列に「あいうえお」が存在することを確認する。
0. 「あいうえおか」を読み込み、対象文字列に「あいうえおか」が存在しないことを確認する。
0. 4.にて「あいうえおか」が存在しないため、「あいうえお」をグループとし、文字列から「あいうえお」を削除する。
0. この時点で対象文字列は「かきくけこかき」
0. 「か」を読み込み、対象文字列に「か」が存在することを確認する。
0. 「かき」を読み込み、対象文字列に「かき」が存在することを確認する。
0. 上記を繰り返し、「かきく」を読み込み、対象文字列に「かき」が存在することを確認する。
0. 9.にて「かきく」が存在しないため、「かき」をグループとし、文字列から「かき」を削除する。
0. この時点で対象文字列は「くけこ」
0. 「く」を読み込み、対象文字列に「く」が存在しないことを確認する。
0. 「け」を読み込み、対象文字列に「け」が存在しないことを確認する。
0. 「こ」を読み込み、対象文字列に「こ」が存在しないことを確認する。

追記
上の間違ってました。すいません。「あいうえおかき」でグループになってしまいますね。
utunさんの言うとおりもう少しルールがないと絞り込めませんね。

utunさんを参考にc#で

lang
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5namespace TestTeraTail
6{
7    class Program
8    {
9        static void Main()
10        {
11            var inputText = "あいうえおかきくけこあいうえおかきあいうえおあいうえお";
12            var result = ExtractGroup(inputText);
13            foreach (var group in result)
14            {
15                Console.WriteLine("Group:" + group 
16　　　　　　　　　　　+ " Count:" + SearchCount(inputText, group));
17            }
18            Console.ReadLine();
19        }
20
21        private static IEnumerable<string> ExtractGroup(string source)
22        {
23            while (source.Length > 1)
24            {
25                var result = Enumerable.Range(0, source.Length)
26                    .Select(i => new { StartIndex = i
27　　　　　　　　　　　　　　, LengthRange = Enumerable.Range(1, source.Length - i) })
28                    .SelectMany(x => 
29　　　　　　　　　　　　　　x.LengthRange.Select(i => source.Substring(x.StartIndex, i)))
30                    .Select(x => new { Group = x, Count = SearchCount(source, x) })
31                    .Where(x => x.Count > 1)
32                    .OrderByDescending(x => x.Group.Length)
33                    .OrderByDescending(x => x.Count)
34                    .FirstOrDefault();
35
36                if (result == null) yield break;
37
38                yield return result.Group;
39                source = source.Replace(result.Group, "");
40            }
41        }
42
43        private static int SearchCount(string source, string x)
44        {
45            return (source.Length - source.Replace(x, "").Length) / x.Length;
46        }
47
48    }
49}

実行結果

Group:あいうえお Count:4                                                             
Group:かき Count:2

投稿2014/11/25 09:25

sho_cs

総合スコア3541

あなたの回答

tips

プレビュー

行動規範の内容に同意します

質問の解決につながる回答をしましょう。サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。また、読む側のことを考えた、分かりやすい文章を心がけましょう。

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう！

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！