문자열 검색 알고리즘

text - 대상 문자열  N  

pattern - 검색할 문자열  M

 

브루트 포스 알고리즘 O(NM)

모두 검사

FString Contains 함수의 경우도 이쪽 계열??

내부에서 (Strnistr Strnstr) 사용하고있음

 

KMP 알고리즘 O(N + M)

 

현재까지 일치했었던 검색어의 부분 문자열 정보 활용

텍스트 포인터가 뒤로가지않고 선형으로 증가

text : pattern = 1 : 1

 

 

실패함수 - 여기까지 맞다가 틀렸을 때 어디로 돌아가야하는지 알려주는 테이블

LPS (Longest Prefix Suffix) - 접두사와 접미사가 일치할때의 (전체문자열 제외한 가장 긴것)

 

 

Pi (Partial Match Table)  ex: [ABCCABE] 

i	0	1	2	3	4	5	6
접두사 (prefix)		A	A AB	A AB ABC	A AB ABC ABCC	A AB ABC ABCC ABCCA	A AB ABC ABCC ABCCA ABCCAB
접미사 (suffix)		B	C BC	C CC BCC	A CA CCA BCCA	B AB CAB CCAB BCCAB	E BE ABE CABE CCABE BCCABE
LPS[i] = π[i]	0	0	0	0	1	2	0

 

즉, LPS 를 구하는 단계 -> O(M)

Text를 스캔하는 단계 -> O(N)

 

 

i / j  1씩 증가하며 차례대로 비교

i=5 / j=5 까지 일치

i=6 / j=6 일 때 불일치  j = LPS[j-1] = LPS[5] = 2 

i=6 / j=2 일 때 불일치  j = LPS[j-1] = LPS[1] = 0

i=6 / j=0 일 때 불일치  j = 0 이므로 i++

i=7 / j =0 ... 계속

 

 

 

아호 코라식 알고리즘 O(N + M1 + M2 + M3 + .. )

text : pattern = 1: N  

한 번에 여러문자 포함되어있는지 검색할 때 좋음

 

브루트 포스 - O(NM1 + NM2 + NM3 + ...)

KMP (N번) - O (N + M1 + N + M2 + N + M3 + ...)

아호 코라식 -O(N + M1 + M2 + M3 + ...)

 

Trie 생성시간 -> O(M1 + M2 + M3 ... )

검색시간 -> O(N) 

 

즉, Trie 한 번 만들어 놓으면 (pattern 데이터가 변하지 않을 때) O(N) 밖에 걸리지않아 가볍다

1. 바보
2. 보보
3. 바보보
4. 띠바보
5. 띠보보
6. 이바보



1) 바보
0 -- '바' --> 1
1 -- '보' --> 2 (bEndPattern = true)


2) 보보
0 -- '보' --> 3
3 -- '보' --> 4 (bEndPattern = true)


3) 바보보
0 -- '바' 이미 있음 → 1
1 -- '보' 이미 있음 → 2
2 -- '보' --> 5 (bEndPattern = true)


4) 띠바보
0 -- '띠' --> 6
6 -- '바' --> 7
7 -- '보' --> 8 (bEndPattern = true)


5) 띠보보
0 -- '띠' 이미 있음 → 6
6 -- '보' --> 9
9 -- '보' --> 10 (bEndPattern = true)


6) 이바보
0 -- '이' --> 11
11 -- '바' --> 12
12 -- '보' --> 13 (bEndPattern = true)


루트 자식 1 / 3 / 6 / 11 은 Fail(n) = 0

0 (root)
├─ 바 (1)
│  └─ 보 (2) *          Fail(2) = 3
│     └─ 보 (5) *       Fail(5) = 4
├─ 보 (3)
│  └─ 보 (4) *          Fail(4) = 3
├─ 띠 (6)
│  ├─ 바 (7)            Fail(7) = 1
│  │  └─ 보 (8) *       Fail(8) = 2
│  └─ 보 (9)            Fail(9) = 3
│     └─ 보 (10) *      Fail(10) = 4
└─ 이 (11)
   └─ 바 (12)           Fail(12) = 1
      └─ 보 (13) *      Fail(13) = 2

 

노드 구조체

struct FACNode
{
    FACNode()
        : Fail(0)
        , bOutput(false)
    {}

    TMap<TCHAR, int32> Next;
    int32 Fail = 0;
    bool bEndPattern;
};

// Next - 지금 문자에서 다른 문자로 이동할 수 있는 링크
// Fail - 지금 문자로 더 이상 진행할 길이 없을 때, 어디로 되돌아가서 다시 계속 검사할지 가리키는 링크
// bEndPattern - 지금 노드가 패턴 끝 문자 인지

 

 

 

void AddPattern(const FString& Pattern)
{
    if (Pattern.IsEmpty())
    {
        return;
    }

    int32 State = 0;

    const int32 Len = Pattern.Len();
    for (int32 i = 0; i < Len; ++i)
    {
        const TCHAR Ch = FChar::ToLower(Pattern[i]);

		// A) 현재 상태(State) 에서 Ch 간선이 이미 존재하는지 검사
        int32* NextStatePtr = Nodes[State].Next.Find(Ch);
        
        // B-1) 링크가 없으면 새 노드 생성
        if (NextStatePtr == nullptr)
        {
            const int32 NewState = Nodes.Num();
            Nodes.AddDefaulted();
            Nodes[State].Next.Add(Ch, NewState);
            State = NewState;
        }
        // B-2) 링크가 이미있으면 이동
        else
        {
            State = *NextStatePtr;
        }
    }

	// C) 패턴 마지막 문자에 도달하면 표시 
    Nodes[State].bEndPattern = true;
}

 

 

Fail 링크

• Fail(2)=3: “바보”의 부모는 “바”(1), Fail(1)=0에서 ‘보’로 가면 3(“보”)가 있으니까.
• Fail(4)=3: “보보”의 부모는 “보”(3), Fail(3) = 0에서 ‘보’로 가면 3(“보”)가 있으니까.
• Fail(5)=4: “바보보”의 부모는 “바보”(2), Fail(2)=3(“보”)에서 ‘보’로 가면 4(“보보”)가 있으니까.
• Fail(7)=1: “띠바”의 부모는 “띠”(6), Fail(6)=0에서 ‘바’로 가면 1(“바”)가 있으니까.
• Fail(8)=2: “띠바보”의 부모는 “띠바”(7), Fail(7)=1(“바”)에서 ‘보’로 가면 2(“바보”)가 있으니까.
• Fail(9)=3: “띠보”의 부모는 “띠”(6), Fail(6) = 0에서 ‘보’로 가면 3(“보”)가 있으니까.
• Fail(10)=4: “띠보보”의 부모는 “띠보”(9), Fail(9)=3(“보”)에서 ‘보’로 가면 4(“보보”)가 있으니까.
• Fail(12)=1: “이바”의 부모는 “이”(11), Fail(11) = 0에서 ‘바’로 가면 1(“바”)가 있으니까.
• Fail(13)=2: “이바보”의 부모는 “이바”(12), Fail(12)=1(“바”)에서 ‘보’로 가면 2(“바보”)가 있으니까.

// 현재가 State / 간선문자가 Ch / 자식이 NextState

void BuildFailLinks()
{
    TQueue<int32> StateQueue;

    // 루트의 자식 노드들은 (첫 단어 읽은상태) 실패했을때 돌아갈 곳은 항상 루트(0) 임
    for (const TPair<TCHAR, int32>& Pair : Nodes[0].Next)
    {
        const int32 Child = Pair.Value;
        Nodes[Child].Fail = 0;
        StateQueue.Enqueue(Child);
    }

    // 나머지 fail  계산
    while (!StateQueue.IsEmpty())
    {
        int32 CurrentState = 0;
        StateQueue.Dequeue(CurrentState);

        for (const TPair<TCHAR, int32>& Pair : Nodes[CurrentState].Next)
        {
            const TCHAR Ch = Pair.Key;
            const int32 NextState = Pair.Value;

            // (A) 현재 노드의 fail 링크 부터 시작
            // AddPattern 에서 만들어진 Tire에 의해 
            // ParentFail는 현재 노드의 가장 긴 접미사 후보
            int32 ParentFail = Nodes[CurrentState].Fail;

            // (B) F에서 Ch로 못 가면 fail 링크로
            // 즉, fail 링크로 갈 때마다 접미사가 줄어듦 (root로 향해 가므로)
            while (ParentFail != 0 && Nodes[ParentFail].Next.Contains(Ch) == false)
            {
                ParentFail = Nodes[ParentFail].Fail;
            }

            // (C-1) ParentFail에서 Ch로 갈 수 있으면 그 도착지가 Fail(NextState)
            // (C-2) 끝까지 못 찾음 (root 까지 내려왔는데도 없음) Fail(NextState) = 0
            const int32* FailNext = Nodes[ParentFail].Next.Find(Ch);
            if (FailNext != nullptr)
            {
                Nodes[NextState].Fail = *FailNext;
            }
            else
            {
                Nodes[NextState].Fail = 0;
            }

            // (D) 지금까지 읽은 텍스트가 어떤 패턴 문자열을 끝까지 읽음
            if (Nodes[Nodes[NextState].Fail].bEndPattern)
            {
                Nodes[NextState].bEndPattern = true;
            }

            StateQueue.Enqueue(NextState);
        }
    }
}

 

가장 긴 접미사 ↓ 더 짧은 접미사 ↓ 더 짧은 접미사 ↓ root

State = "abcabc" ↓ Fail(State) = "abc" ↓ Fail("abc") = "bc" ↓ Fail("bc") = "c" ↓ Fail("c") = root

 

 

'보' 에 대해서만 Fail 링크

데이터상으론 한 글자씩 있는게 맞는데 편하게 보기위해서 접미사 까지 붙인다면 다음과 같은데

각각 가리키고있는 Fail 링크가 최대 접미사 인걸 알 수 있다.

 

 

패턴인지 검색

bool IsContainsProfanityText(const FString& TargetText) const
{
    if (Nodes.Num() == 0 || Nodes.Num() == 1)
    {
        UE_LOG(ZLogTable, Warning, TEXT("[%s] Aho-Corasick Trie not Created Or Table Data is Broken or Empty"), Z_FUNCTIONW);
        return false;
    }

    int32 CurrentState = 0;
    for (TCHAR Element : FStringView{ TargetText })
    {
        const TCHAR Ch = FChar::ToLower(Element);
        while (CurrentState != 0 && Nodes[CurrentState].Next.Contains(Ch) == false)
        {
            CurrentState = Nodes[CurrentState].Fail;
        }

        const int32* NextState = Nodes[CurrentState].Next.Find(Ch);
        if (NextState != nullptr)
        {
            CurrentState = *NextState;
        }

        if (Nodes[CurrentState].bEndPattern)
        {
            return true;
        }
    }
    return false;
}