{"action":"created","issue":{"url":"https://api.github.com/repos/explosion/spaCy/issues/2173","repository_url":"https://api.github.com/repos/explosion/spaCy","labels_url":"https://api.github.com/repos/explosion/spaCy/issues/2173/labels{/name}","comments_url":"https://api.github.com/repos/explosion/spaCy/issues/2173/comments","events_url":"https://api.github.com/repos/explosion/spaCy/issues/2173/events","html_url":"https://github.com/explosion/spaCy/issues/2173","id":310235490,"number":2173,"title":"Rethink storage of parse tree in C data","user":{"login":"honnibal","id":8059750,"avatar_url":"https://avatars3.githubusercontent.com/u/8059750?v=4","gravatar_id":"","url":"https://api.github.com/users/honnibal","html_url":"https://github.com/honnibal","followers_url":"https://api.github.com/users/honnibal/followers","following_url":"https://api.github.com/users/honnibal/following{/other_user}","gists_url":"https://api.github.com/users/honnibal/gists{/gist_id}","starred_url":"https://api.github.com/users/honnibal/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/honnibal/subscriptions","organizations_url":"https://api.github.com/users/honnibal/orgs","repos_url":"https://api.github.com/users/honnibal/repos","events_url":"https://api.github.com/users/honnibal/events{/privacy}","received_events_url":"https://api.github.com/users/honnibal/received_events","type":"User","site_admin":false},"labels":[{"id":111380487,"url":"https://api.github.com/repos/explosion/spaCy/labels/enhancement","name":"enhancement","color":"20834E","default":true},{"id":111380488,"url":"https://api.github.com/repos/explosion/spaCy/labels/help%20wanted","name":"help wanted","color":"f6f6f6","default":true}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2018-03-31T11:56:15Z","updated_at":"2018-04-14T16:40:38Z","closed_at":null,"author_association":"OWNER","body":"## Goal: Make underlying tree storage slightly more efficient, less confusing.\r\n\r\nThere's a lot of ways to store a tree. The one in spaCy was what I came up with off the top of my head when building my previous parser, during my research. I think we can probably improve this, especially since when I designed this initially, the trees were constrained to have no crossing branches. This is no longer true.\r\n\r\n## Current solution\r\n\r\nThe underlying `TokenC` struct stores the parse tree like this:\r\n\r\n```python\r\n\r\ncdef struct TokenC:\r\n    int32_t head # Offset of head, i.e. if attached to word 2 previous, head is -2\r\n    uint32_t l_kids # Count of left children\r\n    uint32_t r_kids # Count of right children\r\n    uint32_t l_edge # Leftmost point of *yield* -- i.e. leftmost descendent\r\n    uint32_t r_edge # Rightmost point of yield -- i.e. rightmost descendent\r\n```\r\n\r\nSo the current baseline uses 160 bits per node for the tree information. I understand there's a huge chapter in Knuth's TAOCP about approaches to this. (I should really buy that...)\r\n\r\n## Requirements\r\n\r\nWe need to support the following methods:\r\n\r\n```python\r\ncdef const TokenC* get_head(const TokenC* child) nogil\r\n\r\ncdef const TokenC* get_left_child(const TokenC* head, int i) nogil\r\n\r\ncdef const TokenC* get_right_child(const TokenC* head, int i) nogil\r\n\r\ncdef int get_left_edge(const TokenC* head) nogil\r\n\r\ncdef int get_right_edge(const TokenC* head) nogil\r\n\r\ncdef int count_left_children(const TokenC* head) nogil\r\n\r\ncdef int count_right_children(const TokenC* head) nogil\r\n\r\ncdef void add_arc(TokenC* tokens, int head, int child, uint64_t label) nogil\r\n```\r\n\r\n## Terminology and example\r\n\r\nI'm using `child` to mean a direct descendant, and `subtree` to mean all direct and indirect descendents. So, let's say we had a tree like this:\r\n\r\n```\r\n        0\r\n       /    \\\r\n      1.0    1.1\r\n    /           \\\r\n   1.0.0      1.1.0\r\n\r\n(The leaves are ordered 1.0.0, 1.0, 0, 1.1, 1.1.0 in the string)\r\n```\r\n\r\n* The children of 0  are 1.0 and 1.1.\r\n\r\n* The head of 1.0 is 0.\r\n\r\n* The head of 1.1 is 0.\r\n\r\n* The subtree of 0 is (1.0.0, 1.0, 0, 1.1, 1.1.0)\r\n\r\n* The left edge of 0 is 1.0.0\r\n\r\n* The right edge of 0 is 1.1.0\r\n\r\n* The left edge of 1.0 is 1.0.0\r\n\r\n* The left and right edges of 1.0.0 is 1.0.0\r\n\r\n## What's where\r\n\r\nFor now it's best to just work in a distinct module, and get tests passing. If we get a good result, the integration will happen in the `spacy.structs` module, and then `spacy/tokens/token.pyx` and `spacy/tokens/doc.pyx`. Later we can also update code in `spacy/syntax/_state.pxd`."},"comment":{"url":"https://api.github.com/repos/explosion/spaCy/issues/comments/381342201","html_url":"https://github.com/explosion/spaCy/issues/2173#issuecomment-381342201","issue_url":"https://api.github.com/repos/explosion/spaCy/issues/2173","id":381342201,"user":{"login":"skrcode","id":5915832,"avatar_url":"https://avatars1.githubusercontent.com/u/5915832?v=4","gravatar_id":"","url":"https://api.github.com/users/skrcode","html_url":"https://github.com/skrcode","followers_url":"https://api.github.com/users/skrcode/followers","following_url":"https://api.github.com/users/skrcode/following{/other_user}","gists_url":"https://api.github.com/users/skrcode/gists{/gist_id}","starred_url":"https://api.github.com/users/skrcode/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/skrcode/subscriptions","organizations_url":"https://api.github.com/users/skrcode/orgs","repos_url":"https://api.github.com/users/skrcode/repos","events_url":"https://api.github.com/users/skrcode/events{/privacy}","received_events_url":"https://api.github.com/users/skrcode/received_events","type":"User","site_admin":false},"created_at":"2018-04-14T16:40:38Z","updated_at":"2018-04-14T16:40:38Z","author_association":"CONTRIBUTOR","body":"#2221 "}}
{"actor":{"display_login":"skrcode"}}