Создать хэш для хранения и извлечения глаголов на английском языке

Question

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

Обновление: поиск

a) Поиск с постоянным временем O (1) b) Интересные функциидля строк (пример кода)

Answer 1

Ideally I would like to store all of the [verb] forms as 1 hash index

Вы можете подумать, что это почти возможно сделать с так называемыми правильными глаголами, используя какой-то общий фрагмент:

             happen, happens, happened, happened, happening

но это, безусловно, невозможно для так называемых неправильных глаголов:

             eat, eats, ate, eaten, eating
             sing, sings, sang, sung, singing
             go, goes, went, gone, going
             bring, brings, brought, brought, bringing
             speak, speaks, spoke, spoken, speaking

И есть также варианты орфографической замены:

             try, tries, tried, tried, trying
             cry, cries, cried, cried, crying

И другие варианты:

             miss, misses, missed, missed, missing

Я бы предложил создать такую ​​хеш-таблицу для каждой формы глагола, указывая на бесконечную форму; инфинитивная форма указывает на себя:

           verb form  
           infinitive form

например:

          happening
          happen


          went
          go


         happen
         happen

         go
         go


        ate
        eat

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

Answer 2

С нашей точки зрения, это, вероятно, домашнее задание (колледж), так что если это так, вы должны пометить его как «домашнее задание».

В C ++ 0B появился новый официальный стандарт Unordered Map: http://en.wikipedia.org/wiki/Unordered_map_%28C%2B%2B%29

Но если это домашнее задание, то вам может потребоваться реализовать это самостоятельно! Создайте массив, подумайте о том, какой может быть хорошая хеш-функция, и запустите ее.

Answer 3

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

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

Answer 4

Поскольку хранилище звучит крайне редко, а извлекаемые звуки похожи на подавляющее большинство случаев с крайней потребностью в производительности, я рекомендую идеальное хеширование. Это совсем не удобно для хранения, так как вам нужно воссоздать весь хэш, но для извлечения результатов будет гарантировано O (1). Ищите «идеальное хеширование» в Google, и вы увидите веб-сайт Боба Дженкина вторым в списке.

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

Answer 5

Одна проблема в том, что многие английские слова могут быть как глаголами, так и существительными, и только контекст определяет, что это такое. Например, «Как вы относитесь к ситуации?». «Возьми» здесь существительное, а не глагол. Готовы ли вы принять метод грубой силы, который приводит к множеству ложных срабатываний?

Кроме того, что вы подразумеваете под "хранить и извлекать глаголы в предложении"? Определить глаголы в предложении, извлечь их, а затем сохранить их в какой-либо базе данных? Может быть, я неправильно понимаю ваше требование?