Разбор строки в C ++ - PullRequest
       78

Разбор строки в C ++

1 голос
/ 05 марта 2009

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

Каждая строка журнала имеет вид

cust_name time_start time_end (IP или URL) *

Итак, IP-адрес, время, время и, возможно, пустой список IP-адресов или URL-адресов, разделенных точками с запятой. Если в последнем списке есть только ip или url, разделителя нет. Если там больше 1, то они разделяются точкой с запятой.

Мне нужен способ разобрать эту строку и прочитать ее в структуру данных. time_start или time_end может быть системным временем или GMT. cust_name также может иметь несколько строк разделенные пробелами.

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

Ответы [ 10 ]

7 голосов
/ 05 марта 2009

Может быть, Boost RegExp lib поможет вам. http://www.boost.org/doc/libs/1_38_0/libs/regex/doc/html/index.html

5 голосов
/ 05 марта 2009

У меня был успех с Boost Tokenizer для такого рода вещей. Он помогает разбить входной поток на токены с помощью пользовательских разделителей между токенами.

4 голосов
/ 05 марта 2009

Используя регулярные выражения (boost::regex - хорошая реализация для C ++), вы можете легко разделить различные части вашей строки - cust_name, time_start ... и найти все, что urls \ ips

Второй шаг - более детальный разбор этих групп, если это необходимо. Например, даты можно анализировать с помощью библиотеки boost::datetime (написание пользовательского анализатора, если формат строки не является стандартным).

3 голосов
/ 05 марта 2009

Почему вы хотите сделать это в C ++? Это звучит как очевидная работа для чего-то вроде perl.

2 голосов
/ 05 марта 2009

Рассмотрите возможность использования библиотеки Regular Expressions ...

1 голос
/ 05 марта 2009

ОБНОВЛЕНИЕ радикально изменил ответ!

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

Просто имейте в виду, что C ++ не очень поможет с точки зрения эффективности в этой ситуации. Не думайте, что ваша программа будет иметь высокую производительность только потому, что у вас есть быстрый код синтаксического анализа на C ++!

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

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

Хранение огромной структуры данных в памяти очень неэффективно , независимо от того, какой язык вы используете!

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

Если вы это сделаете, вы уже устранили главное узкое место.

Для разбора строки текста, кажется, формат ваших данных довольно упрощен, посмотрите аналогичный вопрос, который я задавал некоторое время назад: Разбор строк C ++ (стиль python)

В вашем случае, я полагаю, вы могли бы использовать поток строк и использовать оператор >>, чтобы прочитать следующую «вещь» в строке.

см. этот ответ , например, код.

В качестве альтернативы (я не хотел удалять эту часть !!) Если бы вы могли написать это на python, это было бы намного проще. Я не знаю вашей ситуации (кажется, вы застряли с C ++), но все же

Посмотрите на эту презентацию для эффективного выполнения таких задач с использованием выражений генератора Python: http://www.dabeaz.com/generators/Generators.pdf

Это стоит прочитать. На слайде 31 он рассматривает то, что кажется очень похожим на то, что вы пытаетесь сделать.

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

1 голос
/ 05 марта 2009

для такой простой грамматики, которую вы можете использовать split, посмотрите на http://www.boost.org/doc/libs/1_38_0/doc/html/string_algo/usage.html#id4002194

1 голос
/ 05 марта 2009

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

0 голосов
/ 06 марта 2009

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

0 голосов
/ 05 марта 2009

Вы можете попытаться использовать простой словарь lex / yacc | flex / bison для разбора такого рода ввода.

...