Microsoft Reinforcement Learning Open Source Fest 2022 — нативный парсер CSV

PR: https://github.com/VowpalWabbit/vowpal_wabbit/pull/4073

Учебник: https://vowpalwabbit.org/docs/vowpal_wabbit/python/latest/tutorials/cmd_csv_with_iris_dataset.html

Введение

Мой проект на Reinforcement Learning Open Source Fest 2022 заключается в добавлении нативной функции разбора CSV для Vowpal Wabbit.

Почему же я решил реализовать парсинг CSV? CSV — один из самых популярных форматов файлов, используемых в наборах данных машинного обучения, и часто предоставляется в качестве формата по умолчанию в таких соревнованиях, как Kaggle. Файлы CSV имеют одну и ту же схему для каждого примера, в то время как текстовый формат VW — нет. Хотя на языках Python и Perl написаны конвертеры, которые преобразуют эти файлы в текстовый формат VW, было бы удобно, если бы VW понимал файлы CSV нативно. Я также хочу бросить вызов самому себе, поскольку в разработке обобщенного парсера для CSV есть удивительно много сложностей, так что этот проект — это не только рассмотрение всех деталей разработки, но и реализация работающего парсера. Мой выбор и потраченное время также окупились, поскольку мой проект уже влился в восходящий поток VW !!!

О CSV

Файлы CSV часто разделяются запятыми (,) или табуляцией. Однако, файлы с альтернативными разделителями часто получают расширение .csv, несмотря на использование разделителя полей без запятой. Такая нечеткая терминология может вызвать проблемы при обмене данными. Многие приложения, принимающие файлы CSV, имеют опции для выбора символа-разделителя и символа кавычек. Точки с запятой (;) часто используются вместо запятых во многих европейских локалях, чтобы использовать запятую (,) в качестве десятичного разделителя и, возможно, точку (.) в качестве символа десятичной группировки.

Разделение полей с помощью разделителя полей — это основа CSV, но запятые в данных должны обрабатываться особым образом.

Как мы работаем с файлами CSV?

Короткий ответ заключается в том, что мы следуем стандартам RFC 4180 и MIME.

Технический стандарт RFC 4180 2005 года формализует формат файла CSV и определяет MIME-тип «text/csv» для работы с текстовыми полями. Однако интерпретация текста каждого поля по-прежнему зависит от конкретного приложения. Файлы, соответствующие стандарту RFC 4180, могут упростить обмен CSV и должны быть широко переносимыми. Вот его требования:

1. Строки должны заканчиваться символами CR или CRLF, причем для последней строки это необязательно.
2. Файлы CSV могут иметь необязательную запись заголовка. Не существует надежного способа определить, присутствует ли она, поэтому при импорте необходимо соблюдать осторожность.
3. Каждая запись должна содержать одинаковое количество разделенных полей.
4. Любое поле может быть заключено в двойные кавычки.
5. Поля, содержащие двойные кавычки или запятые, должны быть заключены в кавычки.
6. Если для заключения полей используются двойные кавычки, то двойная кавычка в поле должна быть представлена двумя символами двойной кавычки.

Копаться в деталях

1. Позволяет указать разделитель полей CSV с помощью —csv_separator, по умолчанию ,, но " | или : зарезервированы и не могут быть использованы, так как двойная кавычка (") служит для экранирования, вертикальная полоса (|) для разделения пространства имен и имен характеристик, : может быть использована в метках.
2. Для каждого разделенного поля автоматически удалите внешние двойные кавычки в ячейке, если они парные. Символы --csv_separator, появившиеся внутри ячеек с двойными кавычками, считаются не разделителем, а обычным строковым символом.
3. Двойные кавычки, которые появляются в начале и конце ячейки, будут считаться заключающими поля. Другие кавычки, которые появляются в других местах и вне заключенных полей, не имеют специального значения. (Так же поступает и Microsoft Excel).
4. Если для заключения полей используются двойные кавычки, то двойная кавычка, появляющаяся внутри поля, должна быть экранирована путем предварения ее другой двойной кавычкой, и этот символ экранирования будет удален при разборе.
5. Использовать строку заголовка для имен функций (и, возможно, пространств имен) / указывать метку и тег, используя _label и _tag по умолчанию. Для каждого разделенного поля в заголовке, кроме тега и метки, может содержаться имя пространства имен и имя признака, разделенные разделителем пространств имен, вертикальной полосой(|).
7. Если количество разделенных полей в текущей строке разбора больше, чем в заголовке, будет выдана ошибка.
8. Обрезает поле на ASCII «белое пространство»(rnfv), а также некоторые UTF-8 BOM символы(xefxbbxbf) перед разделением.
9. Если ни одно пространство имен не разделено, будет использовано пустое пространство имен.
10. Разделитель поддерживает использование t для представления табуляции. В противном случае, при назначении более одного символа, будет выдана ошибка.
11. Прямое чтение метки как строки, интерпретация с помощью парсера текстовых меток VW.
12. Попытается определить, является ли значение признака плавающей или строковой величиной, если NaN, то будет считать его строкой. Кавычки всегда считаются строками.
13. Если значение признака пустое, этот признак будет пропущен.
14. Сброс парсера при достижении EOF файла (для возможной поддержки нескольких входных файлов).
15. Поддержка использования --csv_ns_value для масштабирования значений пространств имен путем указания плавающего отношения. Например, —csv_ns_value=a:0.5,b:0.3,:8, при котором пространство имен a имеет отношение 0.5, b 0.3, пустое пространство имен 8, остальные пространства имен 1.
16. Если все ячейки в строке пусты, то считайте ее пустой строкой. CSV плохо подходит для многострочного формата, о чем свидетельствует множество пустых полей. Многострочный формат часто означает, что разные строки имеют разные схемы. Однако я все равно оставляю поддержку пустых строк, чтобы обеспечить гибкость и расширяемость. В этом случае пользователи все еще могут выражать многострочные примеры в CSV-файлах, хотя это и не указано в списке поддерживаемых. Мы по-прежнему выбрасываем ошибку, если количество полей, разделенных строкой, не совпадает с предыдущим, даже если все поля пустые, поскольку это обычно означает опечатки, которые пользователи могут и не предполагать.

Некоторые статистические данные

Проект достиг 100% покрытия тестов и кода. На моем компьютере для обработки 200000 примеров требуется всего 829 мс, что сравнимо со скоростью разбора файла данных пользовательского формата VW, равной 623 мс, и эквивалентно пропускной способности 21,7 МБ/с.

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

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

• Парсер текста VW:

2239418 bytes parsed in 60581μs
36.9657MB/s

• Неоптимизированный парсер CSV:

1799450 bytes parsed in 912927μs
1.97108MB/s

• Оптимизированный парсер CSV:

1799450 bytes parsed in 87728μs
20.5117MB/s

Моя оптимизация в основном включает в себя превращение всех функций, используемых парсером, в inline. Во время парсинга, вместо того чтобы разбирать столбец за столбцом, я классифицирую все характеристики по их пространству имен и разбираю эти характеристики по пространству имен, чтобы избежать двойной калькуляции хэша пространства имен. Я также заменил map на неупорядоченный map, использую собственную структуру данных vw v_array вместо std::vector и использую реализацию VW parsefloat вместо std::stof, что намного быстрее. Статистика показывает, что это действительно значительно улучшило производительность.

Кредиты

На этом все, спасибо за внимание, а также отдельное спасибо моим наставникам Джеку Герритсу и Питеру Чангу из Microsoft Research — New York City Lab, которые очень помогли мне во время работы над проектом.

Ссылка

1. Значения, разделенные запятыми — Википедия