Разделить строку C не-буквенными символами

Question

Я работаю над программой, которая принимает файл для ввода, читает файл, а затем считает, сколько раз каждое уникальное слово появляется. Мне нужно разделить каждое слово вдоль любого не альфа-символа. Например, aren't станет aren и t, двумя отдельными словами. Как бы я go об этом? В настоящее время я делаю это:

char* test = strtok(buffer, "   1234567890.,':;/\"?!@#$%^&*()'\0'\n");
while (test != NULL){
    BST->root = addToBST(test, BST->root);
    test = strtok(NULL, "   1234567890.,':;/\"?!@#$%^&*()'\0'\n");
    }

Однако это кажется довольно неэффективным, и я уверен, что есть лучший способ сделать это. Есть идеи?

Answer 1

Одной из возможностей будет использование чередующихся вызовов strspn и strcspn для определения длины каждого слова и каждой последовательности межслов. Как только вы знаете начало и длину подстроки, вы можете создать динамически распределяемую копию с strndup или вы можете сравнить с сохраненным словом известной длины с strncmp ,

Это не обязательно самое быстрое решение. Как вы заметили, использование длинной строки разделителей (или не разделителей) требует большого тестирования символов или создания логического вектора, что приводит к большим накладным расходам для кусочков строк, которые могут составлять несколько символов. Тем не менее, это достаточно быстро, и время разработки также важно.

Я перечислил все вышеперечисленное частично, чтобы показать, что современный C в значительной степени превзошел ограничения оригинальной конструкции библиотеки строк и ее зависимость от NUL-завершения, если вы готовы выходить за рамки строковых функций K & R. На практике, однако, я бы, вероятно, написал это в Flex , который эффективно обрабатывает большую часть управления буфером и выполняет сканирование с предварительно вычисленным tr ie (или конечным автоматом), который обычно быстрее, чем все, что вы собираетесь собрать вместе без особых усилий. YMMV. Удачи.

Answer 2

Использование функций strspn() и strcspn() так же хорошо, как вы можете сделать со стандартной библиотекой C, но не очень сложно написать код, который превосходит их, если вы постоянно ищете тот же набор символов, который является общим шаблоном.

Создайте функцию set_span(), которая устанавливает массив из 256 байтов для всех нулей байтов, а затем устанавливает эти символы, перечисленные в строке (это будет поиск аргумент для strspn() или strcspn()) до 1.

Затем создайте функции str_span() и str_cspan(), которые принимают один из инициализированных массивов и строку для поиска. Они могут очень быстро проверить, считается ли каждый символ в строке или нет. Обратите внимание, что имена str_span() и str_cspan() не зарезервированы стандартом C11 ( §7.31.13 ).

Этот код доступен в моем SOQ (Вопросы переполнения стека) в GitHub в виде файла strspan-1.03.tgz в подкаталоге packages . Файлы библиотеки strspan.h и strspan.c; другие файлы предоставляют тестовый код поддержки. Нет кода для помещения strspan.o в библиотеку. (Пакет предполагает, что вы используете GCC; нетрудно изменить makefile для других компиляторов, если вы не используете G CC.)

Я провел несколько тестов для небольшого файла (great.panjandrum) и на большом файле (bible-be.txt - Библия на баси c Engli sh). Результаты синхронизации при обработке каждого файла 3 раза:

$ test2.strspan great.panjandrum great.panjandrum great.panjandrum
# NB: The tests for str_span and strspn are comparable
#     The tests for strlen and strchr are not comparable
strlen   0.000046 (487) great.panjandrum
strlen   0.000031 (487) great.panjandrum
strlen   0.000030 (487) great.panjandrum
strchr   0.000036 (487) great.panjandrum
strchr   0.000030 (487) great.panjandrum
strchr   0.000030 (487) great.panjandrum
str_span 0.000035 (487) great.panjandrum
str_span 0.000032 (487) great.panjandrum
str_span 0.000031 (487) great.panjandrum
strspn   0.000061 (487) great.panjandrum
strspn   0.000052 (487) great.panjandrum
strspn   0.000053 (487) great.panjandrum
$ test.strspan2 bible-be.txt bible-be.txt bible-be.txt
# NB: The tests for str_span and strspn are comparable
#     The tests for strlen and strchr are not comparable
strlen   0.187297 (4467663) bible-be.txt
strlen   0.186324 (4467663) bible-be.txt
strlen   0.187616 (4467663) bible-be.txt
strchr   0.182676 (4467663) bible-be.txt
strchr   0.185405 (4467663) bible-be.txt
strchr   0.184813 (4467663) bible-be.txt
str_span 0.195715 (4467663) bible-be.txt
str_span 0.199516 (4467663) bible-be.txt
str_span 0.194588 (4467663) bible-be.txt
strspn   0.347890 (4467663) bible-be.txt
strspn   0.346028 (4467663) bible-be.txt
strspn   0.347305 (4467663) bible-be.txt
$

Время теста strlen() и strchr() в основном измеряет время чтения и сканирования файлов - strlen() ищет нулевой байт; strchr() ищет новую строку. Первый запуск их означает, что система ввода-вывода хранит файлы в памяти, например, c.

. Время для str_span() и strspn() показывает, что str_span() намного быстрее, чем strspan(). Его можно измерить даже для файла с объемом данных менее 0,5 КиБ; это заметно в файле с объемом данных около 4,5 МБ. JFTR, тестирование проводилось на MacBook Pro 2017 года, работающем под управлением MacOS Mojave 10.14.6 с (скомпилировано в домашних условиях) G CC 9.3.0 и Xcode 11.3.1.

Оба эти теста чередуются с использованием положительного совпадения с последующим отрицательным соответствием.

Обратите внимание, что установочные функции, set_span() и set_ranges(), обе изначально обнуляют аргумент массива (это фактически структура, содержащая массив). Возможно, было бы лучше разрешить им накапливать отдельную функцию set_zero() для сброса структуры (или вы можете использовать memset() - она ​​будет использовать ее).

Answer 3

Не могли бы вы воспользоваться тем фактом, что буквы ASCII в основном являются непрерывными в последовательности десятичных чисел (az: 65-90, AZ: 97-122), чтобы уменьшить количество сравнений, создав собственную версию strtok на основе это общая концепция:

void tokenizer(char* target) {
    int i = 0;
    char test = target[0];
    while (test != '\0') {
        if ((test >= 65 && test <= 90) || (test >= 97 && test <= 122))
            printf("%c", test);
        else {
            printf("\n");
        }
        ++i;
        test = target[i];
    }
}

Затем, возможно, соберите каждое слово в буфер, пропустите его через функцию ha sh, чтобы получить уникальный идентификатор, вставьте его в двоичное дерево поиска в виде структуры (упорядоченной га sh значение, имя слова и счет) для подсчета дубликатов уникальных слов?