C#, 고성능 Tag Search

태그(tag) 조회 성능을 위해 Aho-Corasick 알고리즘을 사용하는데 이를 위해 .NET 9 이상에서 제공하는 SearchValues<string> 함수를 이용하는 예제이다.

최적화 핵심은 그룹화, 길이 내림차순 정렬, FrozenDictionary (읽기 전용 최적화 컬렉션) 자료구조이다. IndexOfAny로 특정 단어로 시작하는 단어들만 루프를 돌게 한다. Greedy Matching (긴 단어 우선), ReadOnlySpan<char>으로 메모리(GC) 최적화 등을 포함한다.

성능을 위해 Parallel.ForEach로 문서를 문단 단위로 나누어 병렬처리할 수 있다.

유의어(Alias) 사전 운영은 {"ID": 1, "Name": "LG", "Aliases": ["LG전자", "LG디스플레이", "LGCNS", "LG CNS"]} 이런 식으로 관리하고, SearchValues 엔진에는 Aliases에 있는 모든 단어를 다 때려 넣고 무엇이 걸리든 결과는 "ID": 1(LG)로 리턴하게 만드는 방식을 사용한다.

Program.cs

using System;  
using System.Collections.Generic;  
using System.Threading.Tasks;  
  
namespace ConsoleApp;  
  
internal class Program  
{  
    private static async Task Main()  
    {  
        // tag dictionary는 DB에서 불러온다고 가정  
        string[] myDictionary =  
            ["삼성전자", "현대차", "LG", "SK하이닉스", "C#", ".NET", "삼성"];  
  
        const string document = "삼성전자는 이번 분기 실적 발표에서 현대차와의 협업을 발표했습니다. 또한 C#과 NET 환경에서의 소프트웨어 최적화가 중요해지고 있으며, SK하이닉스의 반도체 기술도 언급되었습니다."; 
  
        // ~ 10,000 태그 가정  
        TagProcessor tagProcessor = new(myDictionary);  
        List<string> tags = tagProcessor.ExtractAllTags(document);  
        Console.WriteLine($"추출된 태그 개수 : {tags.Count}");  
  
        foreach (string tag in tags)  
        {  
            Console.WriteLine($"- {tag}");  
        }  
  
        Console.WriteLine("----------------------------");  
  
        // 10,000 ~ 100,000개 태그 가정  
        Console.WriteLine("태그 추출 시작 ...");  
          
        List<string> extractTags = await Task.Run(() =>  
        {  
            HighDensityTagProcessor hightProcessor = new(myDictionary);  
            return hightProcessor.ExtractTags(document);  
        });  
          
        Console.WriteLine($"추출된 태그 개수(High) : {extractTags.Count}");  
  
        foreach (string tag in extractTags)  
        {  
            Console.WriteLine($"- {tag}");  
        }  
          
        Console.WriteLine("태그 추출 완료");  
    }  
}

TagProcessor.cs

using System;  
using System.Buffers;  
using System.Collections.Frozen;  
using System.Collections.Generic;  
using System.Linq;  
  
namespace ConsoleApp;  
  
public class TagProcessor  
{  
    // 빠른 위치 점프  
    private readonly SearchValues<string> mTagEngine;  
  
    // 첫 글자로 그룹화하여 검사 대상 최소화  
    private readonly FrozenDictionary<char, string[]> mTagLookup;  
  
    public TagProcessor(IEnumerable<string>? tags)  
    {  
        string[] myDictionary = tags?.Distinct().ToArray() ?? [];  
  
        if (myDictionary.Length == 0)  
        {  
            throw new ArgumentException("태그 리스트가 비어 있어 프로세서를 생성할 수 없습니다.", nameof(tags));  
        }  
  
        mTagEngine = SearchValues.Create(myDictionary, StringComparison.OrdinalIgnoreCase);  
  
        mTagLookup = myDictionary  
            .GroupBy(t => char.ToLowerInvariant(t[0]))  
            .ToDictionary(  
                g => g.Key,  
                g => g.OrderByDescending(t => t.Length).ToArray()  
            )  
            .ToFrozenDictionary();  
    }  
  
    public List<string> ExtractAllTags(string document)  
    {  
        if (string.IsNullOrEmpty(document))  
        {  
            return [];  
        }  
  
        HashSet<string> foundTags = new(StringComparer.OrdinalIgnoreCase);  
        ReadOnlySpan<char> span = document.AsSpan();  
  
        while (true)  
        {  
            // 하드웨어 가속 점프  
            int index = span.IndexOfAny(mTagEngine);  
  
            if (index < 0)  
            {  
                break;  
            }  
  
            span = span[index..];  
            char firstChar = char.ToLowerInvariant(span[0]);  
  
            if (mTagLookup.TryGetValue(firstChar, out string[]? candidates))  
            {  
                bool matched = false;  
                // 현재 남은 문장 길이  
                int spanLength = span.Length;  
  
                foreach (string tag in candidates)  
                {  
                    // 남은 문장보다 태그가 길면 절대 매칭 검사 생략  
                    if (tag.Length > spanLength)  
                    {  
                        continue;  
                    }  
  
                    if (!span.StartsWith(tag, StringComparison.OrdinalIgnoreCase))  
                    {  
                        continue;  
                    }  
  
                    foundTags.Add(tag);  
                    span = span[tag.Length..];  
                    matched = true;  
                    break;  
                }  
  
                if (matched)  
                {  
                    if (span.IsEmpty)  
                    {  
                        break;  
                    }  
  
                    continue;  
                }  
            }  
  
            // 매칭 실패 시 1글자 전진  
            span = span[1..];  
  
            if (span.IsEmpty)  
            {  
                break;  
            }  
        }  
  
        return foundTags.ToList();  
    }  
}

HighDensityTagProcessor.cs

using System;  
using System.Buffers;  
using System.Collections.Frozen;  
using System.Collections.Generic;  
using System.Linq;  
  
namespace ConsoleApp;  
  
public class HighDensityTagProcessor  
{  
    private readonly SearchValues<string> mTagEngine;  
    private readonly FrozenDictionary<string, string[]> mTagLookup;  
    private readonly int mMinTagLength;  
    private readonly bool mUseDoublePrefix; // 2글자 인덱스 플래그  
  
    public HighDensityTagProcessor(IEnumerable<string>? tags, bool useDoublePrefix = true)  
    {  
        string[] tagList = tags?.Distinct().ToArray() ?? [];  
  
        if (tagList.Length == 0)  
        {  
            throw new ArgumentException("태그 리스트가 비어 있어 프로세서를 생성할 수 없습니다.", nameof(tags));  
        }  
  
        mUseDoublePrefix = useDoublePrefix;  
        mMinTagLength = tagList.Min(t => t.Length);  
        mTagEngine = SearchValues.Create(tagList, StringComparison.OrdinalIgnoreCase);  
  
        mTagLookup = tagList  
            .GroupBy(t => GetKey(t, mUseDoublePrefix))  
            .ToDictionary(  
                g => g.Key,  
                g => g.OrderByDescending(t => t.Length).ToArray()  
            )  
            .ToFrozenDictionary(StringComparer.OrdinalIgnoreCase);  
    }  
  
    private static string GetKey(string tag, bool useDouble)  
    {  
        int len = (useDouble && tag.Length >= 2) ? 2 : 1;  
        return tag[..len].ToLowerInvariant();  
    }  
  
    public List<string> ExtractTags(string document)  
    {  
        if (string.IsNullOrEmpty(document) || document.Length < mMinTagLength)  
        {  
            return [];  
        }  
  
        HashSet<string> foundTags = new(StringComparer.OrdinalIgnoreCase);  
        ReadOnlySpan<char> span = document.AsSpan();  
  
        while (span.Length >= mMinTagLength)  
        {  
            int index = span.IndexOfAny(mTagEngine);  
  
            if (index < 0)  
            {  
                break;  
            }  
  
            span = span[index..];  
  
            if (span.Length < mMinTagLength)  
            {  
                break;  
            }  
  
            bool matched = false;  
  
            if (mUseDoublePrefix && span.Length >= 2)  
            {  
                if (TryMatch(span[..2].ToString(), span, foundTags, out int matchedLength))  
                {  
                    span = span[matchedLength..];  
                    matched = true;  
                }  
            }  
  
            if (!matched)  
            {  
                if (TryMatch(span[..1].ToString(), span, foundTags, out int matchedLength))  
                {  
                    span = span[matchedLength..];  
                    matched = true;  
                }  
            }  
  
            if (!matched)  
            {  
                span = span[1..];  
            }  
        }  
  
        return foundTags.ToList();  
    }  
  
    private bool TryMatch(string key, ReadOnlySpan<char> span, HashSet<string> foundTags, out int matchedLength)  
    {  
        matchedLength = 0;  
  
        if (!mTagLookup.TryGetValue(key, out string[]? candidates))  
        {  
            return false;  
        }  
  
        foreach (string tag in candidates)  
        {  
            if (span.Length < tag.Length || !span.StartsWith(tag, StringComparison.OrdinalIgnoreCase))  
            {  
                continue;  
            }  
  
            foundTags.Add(tag);  
            matchedLength = tag.Length;  
            return true;  
        }  
  
        return false;  
    }  
}

throw 대표적인 예외

1.매개변수(인자) 값이 잘못되었을 때

ArgumentNullException: 전달된 인자가 null이면 안 될 때
ArgumentOutOfRangeException: 숫자가 범위를 벗어났을 때
ArgumentException: 그 외에 값이 잘못되었을 때 (포괄)

2.객체의 상태가 올바르지 않을 때

InvalidOperationException: 메서드를 호출하기 위한 전제 조건이 맞지 않을 때
ObjectDisposedException: 리소스가 해제(Dispose)된 객체를 다시 사용하려고 할 때

3.아직 구현하지 않았거나 지원하지 않을 때

NotImplementedException: 메서드 틀만 있고 코드는 없을 때(메모용)
NotSupportedException: 해당 기능이 지원되지 않을 때

Debug.Assert vs if (throw) 차이

구분	Debug.Assert	if (tagList.Length == 0) throw
작동 환경	Debug 모드에서만 작동	Debug/Release 모두 작동
실행 결과	개발 중 팝업창이 뜨거나 로그가 찍힘	프로그램이 예외를 발생시키며 중단됨
용도	개발자의 실수를 잡을 때 (버그 방지)	사용자의 입력값이나 데이터가 잘못되었을 때