Соответствие шаблону строки, суффиксный массив может решить эту проблему или иметь больше решений? - PullRequest
Новая
       25

Соответствие шаблону строки, суффиксный массив может решить эту проблему или иметь больше решений?

1 голос
/ 22 февраля 2012

У меня есть строка, которая генерируется случайным образом специальными символами (B, C, D, F, X, Z), например, для генерации следующего списка строк: 

B D Z Z Z C D C Z
B D C
B Z Z Z D X 
D B Z F
Z B D C C Z
B D C F Z
..........

У меня также естьсписок шаблонов, который должен соответствовать генерируемой строке, возвращать лучший шаблон и извлекать некоторую строку из строки.

шаблон строки 

B D C [D must appear before the C >> DC]
B C F
B D C F
B X [if string have X,must be matched.]
.......

например,

B D Z Z Z C D C Z, которые имеют B и DC, так что могут совпадать с B D C

D B Z C F, которые имеют B и C и F, так что может соответствовать B C F

D B Z D F, которые имеют B и F, так что может соответствовать B F

.......

Теперь, я просто думаю о suffix array.

1.Первое преобразование строки в объект массива суффикса.

2. Обработка каждого шаблона, который находит суффиксМассив может быть сопоставлен.

3.Сравните все сопоставленные шаблоны и получите лучший шаблон. 

var suffix_array=Convert a string to suffix array.
var list=new List();
for (int i=0;i<pattern length;i++){
    if (suffix_array.match(pattern))
        list.Add(pattern);
}
var max=list[0];
for (int i=1;i<list.length;i++){
{
   if (list[i]>max)
      max=list[i];
      Write(list[i]);
}

Я просто считаю, что этот метод сложный, что нужно построить дерево дляшаблон, и принять его в соответствии с суффиксом массива.у кого есть идеи?

==================== update

сейчас я получаю лучшее решение, создаю новоекласс, который имеет свойство B, C, D, X ..., которое является свойством array type.each, сохраняет позицию, которая появляется в строке.Теперь, если B не появляется в строке, мы можем немедленно завершить эту обработку.мы также можем получить все позиции C и D, а затем сравнить их, могут ли они появиться последовательно (DC, DCC, CCC ....)

Ответы [ 2 ]

0 голосов
/ 22 февраля 2012 
var suffix_array=Convert a string to suffix array.
var best=(worst value - presumably zero - pattern);
for (int i=0;i<pattern list array length;i++){
  if (suffix_array.match(pattern[i])){
    if(pattern[i]>best){
      best=pattern[i];
    }
    (add pattern[i] to list here if you still want a list of all matches)
  }
}
write best;

Грубо, в любом случае, если я понимаю, что вы ищете, это небольшое улучшение, хотя я уверен, что может быть лучшее решение.

0 голосов
/ 22 февраля 2012

Я не уверен, какой язык программирования вы используете;Вы проверили его возможности с регулярными выражениями ?Если вы не знакомы с ними, нажмите Google.

...