특징 구조 구현 : 사용할 데이터 유형은 무엇입니까?

Question

단순한 용어로, 피쳐 구조는 속성 - 값 쌍의 정렬되지 않은 목록입니다.

[number:sg, person:3 | _ ], 

가 삽입 될 수있는 :

[cat:np, agr:[number:sg, person:3 | _ ] | _ ], 

[1] 다른 기능 구조 값

[number:[1], person:3 | _ ], 

(즉, 그것이 허용 재진입)에 물건을 서브 인덱스와 공유 할 수있다.

내 질문은 : 어떤 데이터 구조가 사람이가 "유형"그들, 전체 책에

이 등, 2 FTS 사이에 통일을 수행하기 위해, 값으로 나중에 액세스를 구현해야한다고 생각 것 그러나 목록 처리를 단순화하는 lisp에 있습니다. 따라서, 나의 선택은 목록의 해시, 목록의 목록, 또는 트라이입니다. 사람들이 이것에 대해 어떻게 생각하니?

Answer 1

무엇이 값을 구성하는지 조금 더 생각해보십시오. 나는 아마도 일 수있는 간단한 일이 시도 할 것 : 당신이 사업에 있어야 시작할 수 있습니다이 시점에서

typedef struct value { 
    enum { INT, BOOL, STRING, FEATURE_STRUCTURE } ty; 
    union { 
    int int; 
    bool bool; 
    char *string; 
    struct fs *feature_structure; 
    } u; 
} *Value; 

typedef struct fs * { // list of pairs; this rep could change 
    struct avpair *pair; 
    Value value; 
} *Feature_Structure; 

struct avpair { 
    const char *attribute; 
    Value value; 
}; 

당신은

Value mkBool(bool p) { 
    Value v = malloc(sizeof(*v)); 
    assert(v); 
    v->ty = BOOL; 
    v->u.bool = p; 
    return v; 
} 

같은 생성자 함수의 무리를 할 것입니다. "쌍의 목록"이 올바른 표현이 아니라고 판명되면 변경할 수 있습니다. 어떤 작업을 계획하고 있는지 또는 비용 모델에 대한 기대치를 알지 못하면 여기서부터 시작하겠습니다. 그런 다음 좀 더 효율적으로 이동해야한다면, 아마도 삼항 검색 트리를 사용하여 기능 구조를 표현하고 Value에 대해 동일한 표현을 유지해야합니다.