That's quite a question coming from a self-proclaimed non-programmer (are you sure you're not one?)
I didn't use a Trie. The main data structures used are Linked List and Priority Queue.
The tokenization begins by transforming each character to a token. After that merges are applied in priority order as long as merges are possible.
The current state of tokenization is represented as a linked list where each node (token) points to the previous node and next node.
Nodes of the Linked List are added to a Priority Queue _if_ a merge to their corresponding "next node" is possible according to vocabulary (we use a Hash Map to perform these checks fast). Even though we are technically adding nodes of a linked list into the Priority Queue, you can think of the Priority Queue as holding "potential merges" in the order of their priority (priority according to the trained tokenizer merge data).
When we poll a node from the priority queue, we first check that the merge is still possible (because the situation may have changed between the time the node was added to the priority queue, and the time when it was polled from the queue). If the merge is possible, then this is guaranteed to be the most highest-priority merge, so we apply the merge. At this point we need to do several things: we need to mark the previous nodes of the merge as "deleted", we need to create a new node representing the merged token, we need to update the pointers of the adjacent nodes in the linked list, and we need to check if new merges have become possible, and if they have, we need to add the corresponding nodes to the priority queue.
Comments
That's quite a question coming from a self-proclaimed non-programmer (are you sure you're not one?)
I didn't use a Trie. The main data structures used are Linked List and Priority Queue.
The tokenization begins by transforming each character to a token. After that merges are applied in priority order as long as merges are possible.
The current state of tokenization is represented as a linked list where each node (token) points to the previous node and next node.
Nodes of the Linked List are added to a Priority Queue _if_ a merge to their corresponding "next node" is possible according to vocabulary (we use a Hash Map to perform these checks fast). Even though we are technically adding nodes of a linked list into the Priority Queue, you can think of the Priority Queue as holding "potential merges" in the order of their priority (priority according to the trained tokenizer merge data).
When we poll a node from the priority queue, we first check that the merge is still possible (because the situation may have changed between the time the node was added to the priority queue, and the time when it was polled from the queue). If the merge is possible, then this is guaranteed to be the most highest-priority merge, so we apply the merge. At this point we need to do several things: we need to mark the previous nodes of the merge as "deleted", we need to create a new node representing the merged token, we need to update the pointers of the adjacent nodes in the linked list, and we need to check if new merges have become possible, and if they have, we need to add the corresponding nodes to the priority queue.