유한 오토마타 변환을위한 공간 및 시간 효율적인 인코딩

Question

필자는 유한 오토 마톤을위한 변환을 효율적으로 인코딩하는 방법에 대해 생각해 왔으며 또한 빠른 검색 시간을 보장합니다. 나에게 좋은 생각이 들었다면, int 당 비트 단위로 전환 심볼을 1 또는 0으로 효율적으로 인코딩하기 위해 상태 당 최대 32 개의 출력 전환이 있음을 알고 있다면 예제 int를 사용하는 것이 좋습니다.

그래서 T 타입 (예 : 문자열)을 int로 매핑하는 클래스가 있습니다. ID (문자열)는 문자열이 정수 인코딩으로 할당 된 ID를 반환합니다. 문자열 "fish", "cat"및 "tree"를 하나씩 빈 ID 객체에 추가하면 "fish"에 0, "cat"에 1, "tree"에 2가 할당됩니다.

나중에 2의 제곱을 개별 전이 기호와 연결합니다. 전원은 전환 심볼에 지정된 ID로 결정됩니다. 아이디 클래스는 오히려 "물고기", "고양이"와 "나무"보다 영어 알파벳을 공급 되었다면

결과 매핑이 될 것

a : 0 
b : 1 
c : 2 
... 
j : 9 
... 
z : 26 

나가는 가장자리 "를 갖는 국가의 outgoing_symbols 필드 는 ","C ","E "및"F "는 그러므로 다음과 같을 것이다 :

이제 간단히 state.outgoing_symbols + = POW (2, ID (transition_symbol))를 수행 할 수

00000000 00000000 00000000 00110101 
     zy xwvutsrq ponmlkji hgfedcba 

로의 천이를 추가 할 때 기존의 상태.

제가 단일 INT 32 개 심볼을 저장할 수 있고, I 여부 상태를 일정 시간 질의 할 수 있다는

00000000 00000000 00000010 00110101 
     zy xwvutsrq ponmlkji hgfedcba 

이 표현의 이점을 수득 outgoing_symbols 2^9 추가 state.outgoing_symbols+=pow(2,ID(j)) 할 것이다

델타 상태 맵핑이

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ 
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │...│ │ │ │ │ │ │ │ │ │ │ n │ 
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ 
└───┴───┴───┴───┴───┴───┴───┴─┬─┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 
           │ 
           │ 
           │ 
           │ 
           │ 
           ├───────────────────────────────────────────────────────────────────────┐ 
           │ sym_enc outgoing_symbols  00000000 00001000 10000010 00110100 │ 
           │                  │ 
           │ T mapping_of_symbols_onto_target_states        | 
           └───────────────────────────────────────────────────────────────────────┘ 

같은 구조체의 벡터라고 가정 : 그들은 주어진 기호로의 전이가 0에서 n까지의 구조체는 outgoing_symbols이고 심볼은 대상 상태로 매핑됩니다. 가장 큰 문제는 내가 지금까지 목표 상태로 전환 기호 관련이없는 것을 내가 효율적인 인코딩과 함께 전환이 매우 효율적인 인코딩을 사용 할 수있는 방법을 생각할 수 없다

bool has_outgoing_symbol(int state, int symbolID) 
{ 
    return delta[state].outgoing_symbols & pow(2, symbolID) == symbolID; 
} 

: 그럼이 기능을 쓸 수 있습니다 필요한 매핑의.

나는 2 개의 벡터를 가질 수 있는데, 하나는 전이 심볼 ID와 대상 상태의 ID를 저장하는 하나의 벡터 벡터이다. 두 벡터는 "동기화"될 것이므로 모든 i에 대해 vector1[i]은 vectpr2[i]에 해당합니다. 두 벡터가 아닌 형태

struct transition 
{ 
    std::vector to_states; 
    int transition_symbol; 
}; 

의 구조체의 1 개 벡터를 가지고있는 이유는 내가 오히려 하나 개의 벡터보다 간단한 유형의 몇 가지 벡터가 더 잘 어디 분명히 이해하지 않는 일부 프로세서 마법을 사용하는 것입니다 간단한 유형의 구조체.

선형 또는 로그 조회 유형에서 대상 상태를 조회해야하는 경우 인코딩 2를 거쳐 전환 심볼에 대한 상수 조회를 사용하면 2의 누승으로 낭비됩니다. 그러나 기호를 대상 상태에 매핑하기 위해 해당 인코딩을 사용하는 방법을 생각할 수는 없습니다.

아무도 나에게 이런 식으로 또는 어쩌면 곧장 똑같이 읽는 방법에 대한 제안을하는 방법을 가지고 이것을 할 수 있습니까?

Answer 1

정확하게 이해하면 비트 마스크에 비트가 설정된 각 심볼에 대해 벡터에 항목을 저장하고 심볼이 지정된 항목을 효율적으로 검색하려고합니다.

int getSymbolIndex(int state, int symbolID) 
{ 
     if(symbolID == 0) 
     return 0; 
    return NumberOfSetBits(delta[state].outgoing_symbols & ((1 << symbolID) -1)); 
} 

사용하여 인덱스를보고 반환 :이 경우

, 당신은 낮은 확인하려는 것보다는 모든 기호의 마스크에 설정된 비트의 수를 계산하여 항목의 인덱스를 계산할 수 있습니다 상태에 대해 저장된 대상 상태의 벡터에 항목을 올립니다. 실제로는 세트에있는 기호에 대해서만 유효한 결과를 제공합니다. 이 질문에 대한 참조 정수의 비트 수를 계산하기위한 효율적인 방법을

: How to count the number of set bits in a 32-bit integer?