文字列リストをTRIE Optimizeされた正規表現に
Posted feedbacks - C#
とりあえず素朴に。例題データ読ませると「^program(?:|(?:ist(?:|ic)|m(?:a(?:|(?:r|ti(?:c(?:|ally)|st)))|er)))$」を吐きます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | using System;
using System.Collections.Generic;
using System.IO;
static class Program {
public static void Main(String[] args) {
// 行ごとに読み込んで
List<string> words = new List<string>();
using(StreamReader sr = new StreamReader(args[0])) {
foreach(string line in sr.ReadToEnd().Split('\n', '\r')) {
if (line != string.Empty && !words.Contains(line)) {
words.Add(line);
}
}
words.Sort();
}
// 重複文字数をチェックして
List<int> indexes = new List<int>(); {
int[] itemp = new int[words.Count];
for(int i = words.Count - 1; 1 <= i; i--) {
int to = Math.Min(words[i - 1].Length, words[i].Length);
for(int j = 0; j < to && words[i - 1][j] == words[i][j]; j++) {
itemp[i]++;
}
}
indexes.AddRange(itemp);
}
// 重複文字数を多い順に並び替えて
List<int> times = new List<int>(); {
foreach(int cnt in indexes) {
if (!times.Contains(cnt))
times.Add(cnt);
}
times.Sort();
times.Reverse();
}
// 重複部分を削っていく
foreach(int steps in times) {
for(int i = words.Count - 1; 0 < i; i--) {
if (indexes[i] == steps) {
words[i - 1] = string.Format("{0}(?:{1}|{2})",
words[i - 1].Substring(0, steps),
words[i - 1].Substring(steps),
words[i].Substring(steps));
words.RemoveAt(i);
indexes.RemoveAt(i);
}
}
}
string result = "^" + words[0] + "$";
Console.WriteLine(result);
}
}
|
dankogai
#4038()
[
Perl
]
Rating0/2=0.00
これは、実例を見た方が簡単だと思います。 CPANにRegexp::Assembleというモジュールがあるのですが、要はこれの簡易版を作って欲しいということです。私自身、同様のことを行うモジュールを過去にいくつか作っています(e.g Regexp::Optimizer)。
ここでは、文字列のリストを受け取って、それをTRIE化した正規表現に出来ればOKです。Regexp::AssembleやRegexp::Optimizerは正規表現を受け取ってそれをTrie化することも可能ですし、Perl 5.10では内部的にTrie Optimizationを行ったりするのですが、そこまでの機能は求めません。
なお、ここで言う「正規表現」は、必ずしもPerl互換のものである必要はありません。それがTrieになっていることをきちんと示せればOKです。
とはいうものの、Perl5互換になっていた方が、サポートしている環境が多くて有用性は高そうです。可能であればそうして下さい。
Dan the Regexp Assembler
see: Trie (en.wikipedia)
Rating0/2=0.00-0+
[ reply ]