Парсинг данных

[Дмитрий Макеев]

Добрый день!

Возможно кому-то покажется вопрос довольно простым, но я за неимением опыта не знаю как лучше сделать.

Задача распарсить бинарную последовательность (IOList) по определенным правилам. С паттерн матчингом все ясно, т.е. если делать например вот так:

case Data of

   <<"msg",Params/binary>> -> {ok,msg,Params}

   ..

То все нормально происходит, но если например мне нужно вытащить данные из середины, например так: <<"msg",Params/binary,"end">> - то это уже не проходит, т.к. неограниченные длины в матчинге допустимы только в конце.

Ну и если ограничения у меня не длинами, а каким-то разделительными символами, то такой вариант тоже не пойдет (по крайней мере в чистом виде).

Как лучше поступить? обработчик списка, типа parse([H|T],state)-> ... Смотреть каждый байт, сверяться с правилами и в стэйте таскать всякую информацию о текущем ходе парсинга? Или написать например порт на C? (не знаю правда делают так или это не имеет смысла) Или есть еще какие-то встроенные средства о которых стоит знать?

В общем, прошу поделиться "лучшими практиками" в этих вопросах.

[Andrew Gopienko]

Есть еще binary:split, re:run

Возможно подойдут для вашей задачи.

16 декабря 2013 г., 20:52 пользователь Дмитрий Макеев <dire...@gmail.com> написал:

--
Вы получили это сообщение, поскольку подписаны на группу Erlang по-русски.
 
Чтобы отказаться от подписки на эту группу и перестать получать из нее сообщения, отправьте электронное письмо на адрес erlang-russia...@googlegroups.com.
Чтобы добавлять сообщения в эту группу, отправьте письмо по адресу erlang-...@googlegroups.com.
Настройки подписки и доставки писем: https://groups.google.com/groups/opt_out.

[Дмитрий Макеев]

Спасибо за re, интересная вещь.

Буду разбираться, не факт, что мне подойдут, но все равно спасибо!

понедельник, 16 декабря 2013 г., 17:59:02 UTC+4 пользователь Andrew Gopienko написал:

[Максим Ильин]

Добрый день!

  Я парсю так к примеру:

    parse(<<$m, $s, $g, $;, _Tail/binary>>, Rest) 

    parse(<<_El, Tail/binary>>, Rest) ->

        parse(Tail, Rest)

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

    

2013/12/16 Дмитрий Макеев <dire...@gmail.com>

--
З повагою,

Максим Ільїн

[Дмитрий Макеев]

Спасибо, по сути это обычный обработчик списка, но вроде были какие-то упоминания о том, что они недостаточны быстры и лучше использовать что-то из lists (если возможно, например перевернуть список). Но я тоже думаю, что на небольших сообщениях это не сильно заметно будет.

понедельник, 16 декабря 2013 г., 18:42:36 UTC+4 пользователь Максим Ильин написал:

[Дмитрий Макеев]

Отвечу сам себе, на случай если кто столкнется с такой задачей. Для разделения по конкретным символам (или последовательностям) хорошо использовать binary:split (http://www.erlang.org/doc/man/binary.html#split-2) в случае если у вас бинарные данные.

вторник, 17 декабря 2013 г., 12:02:22 UTC+4 пользователь Дмитрий Макеев написал:

[Michael Uvarov]

Попробуй binary:split

--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

[Sergey Prokhorov]

Вполне можно и побайтово просматривать входной поток, так например делает https://github.com/mochi/mochiweb/blob/master/src/mochiweb_html.erl но это относительно медленный вариант в Erlang.

Гораздо быстрее работает binary:split и binary:match (они реализованы на C и используют некоторые оптимизации, особенно если ищем несколько разделителей a-la binary:match(Bin, [Delim1, Delim2, Delim3]) )

понедельник, 16 декабря 2013 г., 17:52:58 UTC+4 пользователь Дмитрий Макеев написал:

[Max Lapshin]

Парни, вы сейчас распространяете непроверенный миф.

Побайтовая обработка бинаря легко может быть быстрее чем binary:split.  Да, binary:split написан на C. Но он очень много чего ещё делает и поэтому не обязательно быстрее.

[Valery Meleshkin]

Для побайтовой обработки могут включаться оптимизации, а могут и нет. Вот тут всё очень хорошо расписано. split/match совершенно не обязательно быстрее.

вторник, 17 декабря 2013 г., 19:37:37 UTC+4 пользователь Sergey Prokhorov написал:

[Sergiy Kostyushkin]

Это не миф, binary:split реально быстрее побайтовой обработки, но его можно ускорить еще, если написать свою собственную реализацию используя binary:match.

Пример моей реализации из exomler:

split(Bin, Pattern) ->
    case binary:match(Bin, Pattern) of
        {A,B} ->
            <<Before:A/binary, _:B/binary, After/binary>> = Bin,
            {Before, After};
        nomatch ->
            {Bin, <<>>}
    end.

Вівторок, 17 грудня 2013 р. 18:41:08 UTC+2 користувач Max Lapshin написав:

[Sergiy Kostyushkin]

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

Вівторок, 17 грудня 2013 р. 22:51:57 UTC+2 користувач Valery Meleshkin написав:

[Mikhail Gusarov]

Быстрее/медленнее/миф/не миф.

Лучше тесты гонять на конкретных примерах вместо того, чтобы доверять
общим утвержденям.

Best regards,
Mikhail Gusarov.


2013/12/17 Sergiy Kostyushkin <s.kost...@gmail.com>:

[Sergiy Kostyushkin]

Вы абсолютно правы. Лучше тестов ничего нет, если задача не слишком ограничена во времени.

Середа, 18 грудня 2013 р. 00:21:17 UTC+2 користувач Mikhail Gusarov написав:

[Sergey Prokhorov]

Я просто на практике столкнулся: Допустим парсим мы HTML/XML такого вида

<div>lorem ipsum ........100500 символов....<b>GREAT!</b>......</div>

Допустим мы обработали '<div>' и теперь нам нужно найти закрывающий токен '</' либо открывающий токен вложенного тега '<' для '<b>' (а для случая <script>...</script> лучше искать не '</' а целиком '</script>'). Тут нужно побайтово пройтись по всему 'lorem ipsum ...' и на каждом байте сделать проверку на несколько байтов вперёд (встретили '<' а что там дальше? '</' или '</script>' или ещё что то).

В binary:match во первых эти проверки осуществляются в сишечке, следовательно меньше работать GC эрланга, считать инструкции и т.п.

Во вторых, binary:match использует дополнительные алгоритмические оптимизации https://github.com/erlang/otp/blob/e0ecc86e35475b434efa6cccba44074ca1040b7a/erts/emulator/beam/erl_bif_binary.c#L42

В частности, Boyer Moore для поисков типа binary:match(Bin, <<"</script>">>) и Aho-Corasick для поиска одного из нескольких шаблонов binary:match(Bin, [<<"<">>, <<"&">>]).

Я, кстати, переписал mochiweb_html с использованием binary:match и, судя по fprof, ускорил на порядок (единственное что, когда я это делал, то не учёл оверхед собственно от fprof, но прод-система стала заметно меньше грузить CPU).

Понятно, что на ваших данных результаты могут быть обратными, но мне binary:match сильно помог.

вторник, 17 декабря 2013 г., 20:41:08 UTC+4 пользователь Max Lapshin написал:

[Valery Meleshkin]

Оптимизации хоть завключайся если где-нибудь посреди есть full qualified call, ну и куча других случаев когда оптимизации не работают.

среда, 18 декабря 2013 г., 2:20:47 UTC+4 пользователь Sergiy Kostyushkin написал:

[Dmitry Zuikov]

Я сделал простую библиотечку парсер-комбинаторов, которая позволяет примерно так парсить бинари:

https://gist.github.com/voidlizard/243d8b0f227125d4277a

Если это актуально, могу попробовать как-то оформить 

и куда-нибудь выложить, т.к. сам с удивлением обнаружил, 

что обычные регекспы не работают с binary (хотя 

парсер под другую задачу писался).

[Max Lapshin]

> обнаружил, что обычные регекспы не работают с binary

что именно ты имеешь ввиду?  Модуль re работает с бинарями.