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

Я был бы очень признателен за помощь с этим алгоритмом/псевдокодом.

В основном я ищу слова с определенным шаблоном (неважно каким). У меня есть специальная функция для его определения, которая возвращает 1, если слово соответствует требованиям. Когда это произойдет, второе слово после этого должно быть опущено и не сохранено в выводе. У меня не было проблем с тем, что "выбранные" слова разделены одним "не выбранным" словом. Проблема в том, что делать, когда "избранные" появляются один за другим?

Я подготовил такой псевдокод, чтобы немного прояснить ситуацию. Но, к сожалению, это работает не для всех комбинаций "избранных" и "не выбранных".

Я ввел три счетчика/переменных, которые помогли мне определить позицию, в которой я сейчас нахожусь.

Следующий псевдокод не в логическом порядке!

if (counter == 2 || in_a_row >= 3) {
    erase = 1;
    counter--;
    yes = 0;
    if (!chosen) 
        counter = 0;
}
if (chosen) {
    counter++;
    yes = 1;
    in_a_row++;
} else {
    if (yes = 1) /* yes - is used when the preceeding word is chosen and the next is not chosen, in order to keep track of the counter */
        counter++;
}
if (in_a_row == 5)
    in_a_row = 4; /* just to make sure that counter doesn't go too high */
if (erase == 1)
    /*erasing procedure*/

Если у Вас есть идея попроще или вы видите в ней ошибку, ПОЖАЛУЙСТА, помогите мне. Пытаюсь разобраться 8 часов...


c algorithm pseudocode
person Peter Cerba    schedule 25.08.2012    source источник
comment
Я не полностью понимаю все условия, когда слово должно быть удалено или нет. Итак, это просто общее замечание. Предполагая, что у вас есть весь список слов перед запуском алгоритма (например, вы не работаете в режиме реального времени с вводом с клавиатуры), мой опыт с подобными проблемами заключается в том, что вам нужно стирать из конца в начало списка . Идея состоит в том, чтобы (1) поместить слова в список, затем (2) просмотреть весь список, (3) пометить элементы, которые нужно стереть, (4) просмотреть список в обратном порядке, стирая элементы. Стирание в обратном порядке упрощает ведение бухгалтерского учета.   -  person rpsml    schedule 26.08.2012
comment
@rpsml Я могу без проблем продолжить обработку файла, единственная проблема заключается в том, как решить, какое слово пропустить.   -  person Peter Cerba    schedule 26.08.2012
comment
На самом деле, я не понял проблемы, так как думал, что это довольно тривиально (я, вероятно, что-то упускаю). Мое понимание алгоритма нулевого порядка таково: если триггерное слово находится в позиции i, просто отметьте позицию i+2 для стирания. И это все. Это приведет к тому, что триггерные слова в i и i+1 будут стирать слова в i+2 и i+3. Триггерные слова в i, i+1 и i+2 удалят слова в i+2 (которое само по себе является триггерным словом), i+3 и i+4. Что мне здесь не хватает?   -  person rpsml    schedule 26.08.2012

Ответы (4)


arrow_upward
1
arrow_downward

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

# include <stdio.h>
# include <ctype.h>
# include <string.h>


# define BUFF_SIZE       1024
# define WORD_DELIM     " "
# define MATCH_PATT     "barf"


int main(  int ac ,  char *av[]  )
{
    __u_char    false = ( 1 == 0 ) ;
    __u_char    true = ( 1 == 1 ) ;

    __u_char    match_1_back = false ;
    __u_char    match
barf   barf  barf   healthy     feeling     better   barf  barf barf uh oh sick again
barf   barf  healthy     feeling     better   barf  barf uh oh sick again
barf   healthy     barf   feeling     better     barf   uh   barf   oh sick again
barf   healthy     feeling     better   barf uh oh sick again

back = false ;

    char        line_buff[  BUFF_SIZE  ] ;
    char        *buff_ptr ;
    char        *word_ptr ;


    while (  fgets( line_buff ,  BUFF_SIZE ,  stdin )  )
    {
        puts(  "\nInput line was:  "  ) ;
        puts(  line_buff  )  ;

        puts(  "Output line is:  "  ) ;

        buff_ptr = line_buff ;

        while (  ( word_ptr = strtok( buff_ptr ,  WORD_DELIM )  )  !=  NULL  )
        {
            buff_ptr = NULL ;

            if (  strcmp( word_ptr ,  MATCH_PATT  )  ==  0  )
            {
                // Set these to what they should be for next iteration.
                match
barf   barf  barf   healthy     feeling     better   barf  barf barf uh oh sick again
barf   barf  healthy     feeling     better   barf  barf uh oh sick again
barf   healthy     barf   feeling     better     barf   uh   barf   oh sick again
barf   healthy     feeling     better   barf uh oh sick again

back = match_1_back ;
                match_1_back = true ;

                // Don't output matched token.
            }
            else
            {
                // Don't output token if a token matched 2 tokens back.
                if (  ! match
barf   barf  barf   healthy     feeling     better   barf  barf barf uh oh sick again
barf   barf  healthy     feeling     better   barf  barf uh oh sick again
barf   healthy     barf   feeling     better     barf   uh   barf   oh sick again
barf   healthy     feeling     better   barf uh oh sick again

back  )
                    printf(  "%s " ,  word_ptr  ) ;

                // Set these to what they should be for next iteration.
                match
barf   barf  barf   healthy     feeling     better   barf  barf barf uh oh sick again
barf   barf  healthy     feeling     better   barf  barf uh oh sick again
barf   healthy     barf   feeling     better     barf   uh   barf   oh sick again
barf   healthy     feeling     better   barf uh oh sick again

back = match_1_back ;
                match_1_back = false ;
            }
        }

        printf(  "\n"  ) ;
    }
}

С этим вводом:

barf   barf  barf   healthy     feeling     better   barf  barf barf uh oh sick again
barf   barf  healthy     feeling     better   barf  barf uh oh sick again
barf   healthy     barf   feeling     better     barf   uh   barf   oh sick again
barf   healthy     feeling     better   barf uh oh sick again

Я получил этот вывод:

Input line was:  
barf   barf  barf   healthy     feeling     better   barf  barf barf uh oh sick again

Output line is:  
better sick again


Input line was:  
barf   barf  healthy     feeling     better   barf  barf uh oh sick again

Output line is:  
better sick again


Input line was:  
barf   healthy     barf   feeling     better     barf   uh   barf   oh sick again

Output line is:  
healthy feeling uh oh again


Input line was:  
barf   healthy     feeling     better   barf uh oh sick again

Output line is:  
healthy better uh sick again

Я просто использовал простое сравнение, а не настоящие регулярные выражения. Я просто хотел проиллюстрировать алгоритм. Соответствует ли результат требованиям?

person toes_314    schedule 25.08.2012
comment
Спасибо! Использование выбранного слова звучало так, как будто это слово было выбрано для вывода. - person toes_314; 26.08.2012
comment
Хотя Ваша реализация немного отличается от той, что в задаче. Я хотел бы сказать, что Я ТАК РАД, ЧТО ВЫ МНЕ ПОМОГЛИ, основываясь на этом, я создал свою собственную программу, которая теперь РАБОТАЕТ КАК ШАРМ. С наилучшими пожеланиями ! - person Peter Cerba; 26.08.2012

arrow_upward
1
arrow_downward

Звучит как классическое использование регулярных выражений. Вы не указываете язык, но многие языки поддерживают RegEx.

Следующий сайт является хорошей отправной точкой/справочником по RegEx, если вы с ним не знакомы. http://www.regular-expressions.info/quickstart.html

Вы бы использовали выражение, состоящее из трех частей. Синтаксис ниже взят из памяти, поэтому вам нужно дважды проверить его:

  • (first) — соответствует слову «первый».
  • [\w]*{1,3} - Любое слово, которое повторяется, например, от 1 до 3 раз -
  • (second) — соответствует слову «второй».
person mbliss    schedule 25.08.2012
comment
Не знаю, кто +1, но это просто реклама программного обеспечения. Нет, спасибо, мне нужно использовать простой C. - person Peter Cerba; 25.08.2012
comment
Привет, Питер, Просто чтобы уточнить, что это не реклама программного обеспечения. Регулярные выражения — встроенная функция многих языков программирования. Сайт, на который я дал ссылку, не является тем, с которым я связан, но тем, который я использую в качестве ссылки на регулярной основе. В любом случае, я рад, что вы нашли решение - person mbliss; 27.08.2012

arrow_upward
0
arrow_downward

Что-то вроде этого?

for (i = 0; i<wordcount; i++)
{
    CurrentWord = Words[i]
    if (WordMatchesCritera(CurrentWord))
    {
        if (HavePrecedingWord)
        { 
             success !!!
        } 
        else
        {
            i ++;
            HavePrecedingWord = true
        }
    }
    else
    {
        HavePrecedingWord = false;
    }
}
person podiluska    schedule 25.08.2012
comment
Это совершенно не работает. Представьте себе последовательность: выбрали, выбрали, а не нет. В соответствии с вашим алгоритмом первый выбранный установит Havepreceeding в 1, что удалит selected2 вместо not1. Спасибо, в любом случае - person Peter Cerba; 25.08.2012
comment
@peterkowalski нет - i++ пропустит selected2 - person podiluska; 26.08.2012

arrow_upward
0
arrow_downward

Будет ли это работать?

    matchID = -1;
    eraseID = -1;


    for(i = 0; i < ... ; i++)
    {
         if( wordMatches ( word[i] ) )
         {                  
            matchID = i;     /* found the chosen one */
            eraseID = -1;         
         }
         else 
         {
            if( matchID != -1 ) /* chosen one was found ? */
            {
                 eraseID = i;   /* erase the next non-matching one */
                 break; /* ? done for now  ? */
            }

          }
    }
person shr    schedule 25.08.2012