Помогите составить алгоритм

Ferox · 03.09.2010

Помогите составить алгоритм

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

Дано: есть текст. Знаки текста делятся на три разновидности. Буквы, цифры и спецсимволы. Для простоты можно считать что к спецсимволам относится, допустим, только запятая, пробел и точка. Кроме того, дан список цифровых последовательностей, про которые известно что они находятся в тексте в таком виде что в тексте между цифрами в произвольном порядке вставлены спецсимволы.

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

В задаче требуется найти, как именно данные цифровые последовательности представлены в тексте, то есть найти последовательность вместе со спецсимволами внутри.

Пример текста: "ловрпл лаврпл 56.34,567.87861,4567 лыорап л4р5678агецуа шпо лцдкн адшпд мпцкш", дана цифровая последовательность: "45678" Ответом будет "4,567.8"

vlad7 · 03.09.2010

А насколько большой текст? Если просто просматривать побайтово текст и сравнивать считанный байт с байтом исходной последовательности, учитывая спецсимволы? В чем сложность?

Ferox · 03.09.2010

Наверно таки да - просматривать побайтово. Просто разбаловали нас регулярные выражения.... А размер значения не имеет. регулярные выражения тоже побайтово просматривают.

cyber2 · 03.09.2010

Хммм
В цикле
формируем регексп
к примеру выражение 123
к нему формируем на лету (с помощью оператора поиска и замены и регекспа к выражению) регекспу вида (1[\.\, ]?2[\.\, ]?3[\.\, ]?)
ищем
...
???
profit!!
конец цикла

Vader · 03.09.2010

Вроде бы, ничего сложного:

Код:

>> import re
>> text="ловрпл лаврпл 56.34,567.87861,4567 лыорап л4р5678агецуа шпо лцдкн адшпд мпцкш"
>> seq = ["45678",]
>> for s in seq:
>>	print [result.rstrip(".,") for result in re.findall("".join([number + "[\.\,]?" for number in s]), text)]
['4,567.8']

Или я не до конца понял проблему?

balkauser · 03.09.2010

Vader сказав(ла):
Код:

>> import re >> text="ловрпл лаврпл 56.34,567.87861,4567 лыорап л4р5678агецуа шпо лцдкн адшпд мпцкш" >> seq = ["45678",] >> for s in seq: >> print re.findall("".join([number + "[\.\,]?" for number in s]), text) ['4,567.8']

Потенциальная проблема этого подхода может проявится, если между цифрами допустимо несколько спецсимволов, в смысле наверное нужно "*", а не "?".

Альтернативным решением является предварительная обработка текста в такую структуру: текст без спецсимволов вообще + информация о соответствии каждой позиции в обработанном тексте позиции в оригинальном. Дальше задача решается элементарным поиском числовой строки в обработанном тексте, а "полный" текст получается путем перехода к соответствующим позициям в оригинале.

Vader · 03.09.2010

balkauser сказав(ла):
Потенциальная проблема этого подхода может проявится, если между цифрами допустимо несколько спецсимволов, в смысле наверное нужно "*", а не "?".

Ну это и не проблема вовсе. Заменить "?" на "*" не составит труда. Просто ТС не указал, сколько там может быть символов, поэтому пока будем считать, что один.

balkauser сказав(ла):
Альтернативным решением является предварительная обработка текста в такую структуру: текст без спецсимволов вообще + информация о соответствии каждой позиции в обработанном тексте позиции в оригинальном. Дальше задача решается элементарным поиском числовой строки в обработанном тексте, а "полный" текст получается путем перехода к соответствующим позициям в оригинале.

Всегда придерживался мнения, что "простое лучше сложного"

. Зачем так усложнять-то?

generatorglukoff · 03.09.2010

какие ограничения на размеры?

eugene_kr · 03.09.2010

Что-то мне подсказывает, что нужно использовать "стековый автомат" как в лексических анализаторах. Этот вариант рассматривался?

fatalex · 03.09.2010

Код:

procedure TfSeqMain.Button1Click(Sender: TObject);

const
  SEARCHING_SEQUENCE = '45678';
  SEQUENCE = 'ловрпл лаврпл 56.34,567.87861,4567 лыорап л4р5678агецуа шпо лцдкн адшпд мпцкш';
  ELIMINATED_SYMBOLS = '., ';

type
  TSeqAttributes = record
    iCount,
    iStartPos,
    iFinishPos : integer;
  end;

var
  SA : TSeqAttributes;
  i : integer;

begin
  SA.iCount := 1;
  SA.iStartPos := -1;
  SA.iFinishPos := -1;

  i := 1;
  while (i <= Length(SEQUENCE)) and (SA.iCount <= Length(SEARCHING_SEQUENCE)) do begin
    if Pos(SEQUENCE[i], ELIMINATED_SYMBOLS) <> 0
      then if SA.iCount > 1
             then SA.iFinishPos := SA.iFinishPos + 1 
             else
      else if SEQUENCE[i] = SEARCHING_SEQUENCE[SA.iCount]
             then begin
               if SA.iCount = 1 then begin
                 SA.iStartPos := i;
                 SA.iFinishPos := i-1;
               end;
               SA.iCount := SA.iCount + 1;
               SA.iFinishPos := SA.iFinishPos + 1;
             end
             else if SA.iCount > 1
                    then begin
                      SA.iCount := 1;
                      SA.iStartPos := -1;
                      SA.iFinishPos := -1;
                    end;
    i := i + 1;
  end;

  if SA.iCount > Length(SEARCHING_SEQUENCE)
    then edResult.Text := Copy(SEQUENCE, SA.iStartPos, SA.iFinishPos - SA.iStartPos + 1)
    else edResult.Text := 'Not found';
end;

в данном примере 2 упрощения:
1) ищется только одна последовательность, т.к. непонятно по условию, что делать, если имеем их несколько и они пересекаются в общей последовательности;
2) находится первое вхождение последовательности ...

ну и допущения о способах передачи массивов, размерах одного символа ... эти детали опускаем ...

идём посимвольно, выкидываем спецсимволы, ведём счётчик, который показывает - с каким по номеру символом в поисковой последовательности должно в следующий раз произойти сравнение ...
ну и храним индексы начала и конца найденной последовательности ...

кстати, абс. всё равно - ищем цифровую или буквенную, или цифробуквенную последовательность ...

если чего не понял по условию, тады йой ...

Orshansky · 03.09.2010

Ferox сказав(ла):
В общем брался я за эту задачу уже два раза, к сожалению работающий алгоритм придумать все-таки не удалось, несмотря на кажущуюся простоту задачи.

Дано: есть текст. Знаки текста делятся на три разновидности. Буквы, цифры и спецсимволы. Для простоты можно считать что к спецсимволам относится, допустим, только запятая, пробел и точка. Кроме того, дан список цифровых последовательностей, про которые известно что они находятся в тексте в таком виде что в тексте между цифрами в произвольном порядке вставлены спецсимволы.

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

В задаче требуется найти, как именно данные цифровые последовательности представлены в тексте, то есть найти последовательность вместе со спецсимволами внутри.

Пример текста: "ловрпл лаврпл 56.34,567.87861,4567 лыорап л4р5678агецуа шпо лцдкн адшпд мпцкш", дана цифровая последовательность: "45678" Ответом будет "4,567.8"

Задача интересная. Постановка задачи ниже плинтуса. На весь раздел полтора программиста

Вобщем ищем первое вхождение последовательности вместе со спецсимволами внутри.

Для этого модифицируем КМП:

Код:

include <iostream> 
#include <string> 
#include <vector> 

using namespace std;

int smart_kmp(const string& S, int begin, string& pattern){

    vector<int> pf (pattern.length());

    pf[0] = 0;
    for (int k = 0, i = 1; i<pattern.length(); ++i){
        while(k>0 && pattern[i] != pattern[k])
            k = pf[k-1];

        if (pattern[i] == pattern[k])
            k++;

        pf[i] = k;
    }

    vector<int> v1;
    vector<int> v2;

    for (int k = 0, i = begin; i<S.length(); ++i){

        switch(S[i])
        {
            case ',':
                v1.push_back(k);
            continue;
            case '.':
                v2.push_back(k);
            continue;
        }

        while ((k>0) && (pattern[k] != S[i]))
            k = pf[k-1];

        if (pattern[k] == S[i])
            k++;
        else
            { v1.clear(); v2.clear(); }

        if (k==pattern.length())
        {
            int d = 0;
            for (vector<int>::iterator it = v1.begin(); it!=v1.end(); ++it, d++) {
                pattern.insert(*it+d,",");
            }

            for (vector<int>::iterator it = v2.begin(); it!=v2.end(); ++it, d++) {
                pattern.insert(*it+d,".");
            }

            return (i-pattern.length()+1);
        }
    }

    return -1;
}

int main()
{
    string pattern;
    pattern = "45678";
    cout<<smart_kmp("rq,w.iouoi rqwrqw 56.34,567.87861,4567 fasfas w4f5,6,7.8jlkjl jl lj",0,pattern)<<"Result:"<<pattern<<std::endl;
    pattern = "45678";
    cout<<smart_kmp("rq,w.io45678uoi rqwrqw 56.34,567.87861,4567 fasfas w4f5,6,7.8jlkjl jl lj",0,pattern)<<"Result:"<<pattern<<std::endl;
    pattern = "45678";
    cout<<smart_kmp("rq,w.io4.56,78uoi rqwrqw 56.34,567.87861,4567 fasfas w4f5,6,7.8jlkjl jl lj",0,pattern)<<"Result:"<<pattern<<std::endl;
    pattern = "45678";
    cout<<smart_kmp("rq,w.io45,,,,,,,,,67..........8uoi rqwrqw 56.34,567.87861,4567 fasfas w4f5,6,7.8jlkjl jl lj",0,pattern)<<"Result:"<<pattern<<std::endl;
    return 0;
}

22Result:4,567.8
7Result:45678
7Result:45.6,78
7Result:45,,,,,,,,,67..........8

Тестирование проведено не на всех возможных вариантах.

generatorglukoff · 03.09.2010

Orshansky сказав(ла):
На весь раздел полтора программиста

ок

Orshansky сказав(ла):
Вобщем ищем первое вхождение последовательности вместе со спецсимволами внутри.

Для этого модифицируем КМП:

круто. а просто выкинуть спец. символы - не Судьба?

Orshansky · 03.09.2010

generatorglukoff сказав(ла):
ок

круто. а просто выкинуть спец. символы - не Судьба?

Формализовать вашу веру в судьбу в виде исходного кода корректно работающего алгоритма, не?

si___ · 03.09.2010

хе хе, чето темнит наш ТС
какие "рролдж ить456тббджо ро5679900- 99,,1455"
неужели сложно написать, что он реально хочет, глядешь и велосипедик то не придется изобретать

Orshansky сказав(ла):
Задача интересная. Постановка задачи ниже плинтуса. На весь раздел полтора программиста

Дима, задача не стоит выеденного яйца, даже если б тс не темнил.

Spirit_of_fire · 03.09.2010

регулярные выражения - это не для фероксов и не для дворянства.

Orshansky · 03.09.2010

Spirit_of_fire сказав(ла):
регулярные выражения - это не для фероксов и не для дворянства.

Пожалуйста. Формализуйте ваши мысли, только в виде исходного кода, а то в разделе не все фаталисты. Пишите регулярное выражение, сравним производительность

Spirit_of_fire · 03.09.2010

Orshansky сказав(ла):
Пожалуйста. Формализуйте ваши мысли, только в виде исходного кода, а то в разделе не все фаталисты. Пишите регулярное выражение, сравним производительность

дык написали уже в комментарии нумер 4. какой смысл повторять?
сравнивайте производительность сколько угодно.
там одна строчка кода - у Вас дохренища.

так еще и идентификаторы информативненькие такие: k, d, s, pf, v1, v2..
Дима, это что за гуйня вообще? ты такому студентов учишь?
я за такое рожей по монитору размазываю.

а шо это за стандарты кодирования такие уникальные, что операторы for и if оформлены по разному?
блин, дилетансткое, потенциальное опасное, немасштабируемое...

Orshansky · 03.09.2010

Spirit_of_fire сказав(ла):
дык написали уже в комментарии нумер 4. какой смысл повторять?
сравнивайте производительность сколько угодно.
там одна строчка кода - у Вас дохренища.

так еще и идентификаторы информатиные k d s..
Дима, это что за гуйня вообще? ты такому студентов учишь?
я за такое рожей по монитору размазываю.

Пока я не увидел вашей реализации. У вас есть прекрасный шанс дать простеньким индексам пафосные названия.

Spirit_of_fire сказав(ла):
а шо это за стандарты кодирования такие уникальные, что операторы for и if оформлены по разному?
блин, дилетансткое, потенциальное опасное, немасштабируемое...

Вы хотели сказать стандарты оформления кода программы?

Spirit_of_fire · 03.09.2010

Orshansky сказав(ла):
Пока я не увидел вашей реализации. У вас есть прекрасный шанс дать простеньким индексам пафосные названия.

"не увидел" - это к окулисту.
возьми лупу и перечитай комментарий номер 4.

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

Orshansky сказав(ла):
Вы хотели сказать, стандарты оформления кода?

Что хотел - то и сказал. Это взаимозаменяемые термины.
Станда́рт оформле́ния ко́да или станда́рт коди́рования (англ. coding standards, coding convention или programming style) — набор правил и соглашений, используемых при написании исходного кода на некотором языке программирования.
(с) педивикия.

у Вас на кафедре "лужу-паяю" о таком не знают?
а в "коммерческих структурах", где Вы зарабатываете бананы?
как не назови, а даже такой простой код и то немного по-*****ьному написан.

Orshansky · 03.09.2010

Spirit_of_fire сказав(ла):
"не увидел" - это к окулисту.
возьми лупу и перечитай комментарий номер 4.

Вот этот бред?

Хммм
В цикле
формируем регексп
к примеру выражение 123
к нему формируем на лету (с помощью оператора поиска и замены и регекспа к выражению) регекспу вида (1[\.\, ]?2[\.\, ]?3[\.\, ]?)
ищем
...
???
profit!!
конец цикла

Вы его сможете откомпилировать или транслировать?

Spirit_of_fire сказав(ла):
а рассказать тебе как потом "простенькие индексы" в голове путаются, тем более у другого разработчика?
оно ж када реального опыта нет, то откуда такое знать...

Пожалуйста, приведите ваш вариант ~~названий индексных переменных~~ решения задачи.