2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 
Сообщение13.02.2009, 19:08 


13/02/09
8
Cave писал(а):
Однако заметим, что если слова в словаре имеют вид - в последнем слове....

я ужЕ обращал внимание, что префикс не м.быть отдельным словом (пол и полковник - нельзя)

 Профиль  
                  
 
 
Сообщение13.02.2009, 19:47 
Заслуженный участник


11/05/08
32166
vv40in в сообщении #186107 писал(а):
1. префиксы не могут быть отдельными словами (пол и полковник - нельзя).

тогда Вы откровенно вошли в штопор..

ну, допустим, с полковником Вы как-нить ещё разберётесь. А как Вы поступите со словом, скажем, "полтина"? (я уж не говорю о прочих политурах)

 Профиль  
                  
 
 
Сообщение14.02.2009, 00:33 


13/02/09
8
нашел! нужен алгоритм Ахо-Корасик. он именно для того и создан..

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение23.09.2017, 12:49 


23/09/17
1
Вот такой алгоритм на QT я использовал для проблемы поиска слова в словаре. Сложность pow(log,2).
Заполняется дерево. В элементах дерева количество первых символов для сравнения и слово. Если первые символы совпадают,
то проверяется слово целиком. для заполнения дерева словами функция add_word_to_tree("абак"). для поиска наличия слова в словаре функция find_in_tree(word_tree,"краб"). Просто скопировать код в QT программу и исправить, если что возникло.

Изображение
Код:
class tree_node {
public:
    tree_node():right(NULL),left(NULL){}
    ~tree_node() { delete right; delete left; }

    int cnt;
    QString word;
    tree_node* right;
    tree_node* left;
} *word_tree = NULL;

void recu_add_word(tree_node* node, QString word)
{
    if (node->word.left(node->cnt) == word.left(node->cnt))
    {
        if (node->left == NULL)
        {
            node->left = new tree_node();
            node->left->word = word;
            node->left->cnt = node->cnt + 1;
        } else {
            recu_add_word(node->left, word);
        }
    } else {
        if (node->right == NULL)
        {
            node->right = new tree_node();
            node->right->word = word;
            node->right->cnt = node->cnt;
        } else {
            recu_add_word(node->right, word);
        }
    }
}

void add_word_to_tree(QString word)
{
    if (word_tree == NULL)
    {
        word_tree = new tree_node();
        word_tree->word = word;
        word_tree->cnt = 1;
    } else {
        recu_add_word(word_tree, word);
    }
}

int find_in_tree(tree_node *node, QString word)
{
    int ret = 1;
    if (node == NULL) return 1;
    if (node->word.left(node->cnt) == word.left(node->cnt)){
        if (node->word == word)
            ret = 0;
        else
            if (ret != 0)
                ret = find_in_tree(node->left, word);
    } else
        if (ret != 0)
            ret = find_in_tree(node->right, word);
    return ret;
}

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение02.10.2017, 22:27 


15/11/15
916
weterok1989 в сообщении #1249970 писал(а):
Вот такой алгоритм на QT я использовал для проблемы поиска слова в словаре.
Вы решили другую задачу, ТС искал слова словаря в слове ) Ваша задача проще. Не вижу особого смысла писать алгоритмы сегодня. Проще закинуть словарь в бд и делать запросы для поиска )

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение02.10.2017, 22:33 
Заслуженный участник


27/04/09
28128
Слово в словаре можно вполне эффективно искать, взяв любую структуру данных из стандартной библиотеки языка, реализующую множество. Обычно это хитрые деревья и чуть менее хитрые хеш-таблицы, но знать эти детали не обязательно (а вот временные сложности разных операций обычно полезно, и их часто указывают в документации). А вот БД это оверкилл, извините. :D

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение02.10.2017, 23:11 


15/11/15
916
arseniiv в сообщении #1252588 писал(а):
БД это оверкилл

Неужто? Это дерево, как я понял, хранится же целиком в памяти? А если словарь содержит миллион слов? 10 миллионов? Может, в упоминаемых библиотеках эти проблемы и решены, конечно. Но БД в данном случае - не оверкилл )
Ну и мороки с обработкой массива не оберешься. Добавлять новые слова, например, затруднительно.

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение02.10.2017, 23:30 
Заслуженный участник


27/04/09
28128
gevaraweb в сообщении #1252597 писал(а):
А если словарь содержит миллион слов? 10 миллионов?
Если. Не будем забывать, что исходный вопрос был не понят weterok1989, и его вариант, который мы обсуждаем, не выписан в деталях, так что давайте я вас тоже спрошу, а что если в дереве сто элементов, а вы предлагаете БД. Кроме того, я, конечно, не в курсе, как мейнстримные (не-NoSQL) СУБД исполняют запрос «есть ли в таблице из одного столбца строка с таким-то значением», но что-то мне подсказывает, что не быстрее, чем линейно. Это не для всех применений приемлемо.

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение03.10.2017, 00:25 


15/11/15
916
arseniiv в сообщении #1252603 писал(а):
а что если в дереве сто элементов

Дык тогда ему не нужны и ваши хитрые дерева. Поиск в СУБД оптимизирован. Например. В mysql поле можно индексировать (поставив галочку), тогда поиск становится бинарным. А это почти тот же поиск по дереву.

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение03.10.2017, 00:44 
Заслуженный участник


27/04/09
28128
Ну, хорошо, если так, но всё равно в общем случае не единственный верный вариант.

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение04.10.2017, 15:38 


28/07/17

317
vv40in в сообщении #186062 писал(а):
Задача состоит в поиске слов из словаря в случайных данных любого размера(напр. в файле).

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

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

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение04.10.2017, 17:37 
Заслуженный участник


27/04/09
28128
FomaNeverov
Даже если ТС в своём последнем (на данный момент не только в этой теме, но и на форуме вообще) сообщении, по-вашему, сам себя надул, это было в 2009 году. Давайте, что ли, быть немного внимательными.

Судя по тому, что он писал, Ахо—Корасик вполне себе подходящая вещь, и работающая даже если бы его условия о том, что слова словаря не являются префиксами друг друга, не было. А вы, кстати, даже не описали, последовательный перебор слов или символов исследуемого слова. Без последнего, конечно, никак обойтись нельзя, а вот если вы имели в виду первое…

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение21.01.2018, 11:13 


15/11/15
916
Кстати, попалась задача, неожиданно сводится к этой:
vv40in в сообщении #186062 писал(а):
Есть редко изменяемый словарь. В нём 50000 и более слов, длина слова ~100 символов.
Задача состоит в поиске слов из словаря в случайных данных любого размера(напр. в файле).

Задача такая - обнаружить, присутствует ли слова из ненормативной лексики в указанном тексте. Соответственно, имеется словарь нехороших слов (~4000).

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение21.01.2018, 13:25 
Заслуженный участник


27/04/09
28128
Тут разве не проще составить развесистый регэксп и скомпилировать? Для задачи с громадным множеством длинных и непохожих слов это не так уж подходит, а тут почему не? Заодно можно учесть границы слов по надобности, чтобы не срабатывало в середине безобидных слов типа «рубля» — регэксп тут справится намного лучше, чем добавление неизвестного числа записей, учитывающих все допустимые символы, которые могут встречаться перед началом или после конца слова (в принципе, чуть ли не весь уникод).

 Профиль  
                  
 
 Re: поиск слова из словаря в данных
Сообщение21.01.2018, 13:54 


15/11/15
916
Имеется в виду, потом проверить в цикле 4000 раз? может проще, хотя не уверен. Задача для веб, поэтому язык будет интерпретируемым.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 68 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group