实现基于搜索历史的 trie

Question

我正在为医生制作一个网页，我需要从数据库中为医生检索药物。医生可以输入 complete/partial 药物名称，我需要预测他可以输入什么。简单吗？

现在，我还需要搜索 space 根据过去的操作修改自己。例如，如果许多医生键入 flaxi 而不是氧氟沙星（坏的例子），我的数据结构应该被修改以在键入 flaxi 时反映氧氟沙星。我正在考虑使用特里树，其中每个节点都包含要显示的药物列表。有人可以帮助我了解如何实施吗？

谢谢！！！

Answer 1

这里有一段非常简单的 trie C 代码...希望这可以帮助您理解这些概念...

这是定义节点的方式...

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* Prefix Trie */

typedef struct TrieNode {
    char wordEnd;   // 1 if a word ends at this node, 0 o.w.
    struct TrieNode *index[128];
} TrieNode;

以下是在内存中创建新节点的方法。

TrieNode* makeTrieNode() {
    TrieNode* node = (TrieNode*) malloc (sizeof(TrieNode));
    node->wordEnd = 0;
    return node;
}

以下是在现有的 trie 中递归插入新节点的方法。

TrieNode* insert(TrieNode* root, char* word) {
    TrieNode* child;

    if (*word == 0) {
        root->wordEnd = 1;
        return root;
    }

    child = root->index[*word];
    if (child == NULL) {
        child = makeTrieNode();
        root->index[*word] = child;
    }

    return insert(child, word+1);
}

以下是递归搜索关键字的方法。

// returns 1 if word found 0 o.w.
int search(TrieNode* root, char* word) {
    if (*word == 0) {
        return root->wordEnd;
    }
    if (root->index[*word] == NULL) {
        // unsuccessful search
        return 0;
    }
    search(root->index[*word], word+1);
}

这是小单元测试。

int main() {
    TrieNode *root = makeTrieNode();
    insert(root, "abacus");
    insert(root, "cat");
    insert(root, "can");
    insert(root, "continue");
    insert(root, "continuation");

    printf("%d %d %d %d %d\n", search(root, "abacus"), search(root, "cat"),
    search(root, "cot"), search(root, "continue"),
    search(root, "continuation"));
    return 0;
}

实现基于搜索历史的 trie

Implement trie based on search history

search

search-engine

information-retrieval

trie

data-retrieval