Bitap 근사 문자열 검색 계산기
패턴을 비트마스크로 바꿔 몇 글자 틀려도 찾는 Bitap(Shift-And) 검색을 보여줍니다. 글자마다 상태 비트가 어떻게 밀려 가는지 표로 보이고, 편집거리의 세 연산이 세 갈래 비트 연산에 그대로 대응하는 것을 확인할 수 있습니다.
5,000글자까지.
31글자까지. 상태가 정수 하나에 들어가야 합니다.
0이면 정확한 검색. 바꿔 넣기·빠뜨리기·끼워 넣기를 모두 셉니다.
1글자까지 틀려도 되게 찾은 자리
2군데
정확히 맞는 자리는 0군데였습니다. 오차를 허용하니 2군데가 더 걸렸습니다.
찾은 자리
| 끝나는 자리 | 틀린 글자 | 그 언저리 |
|---|---|---|
| 5 | 1 | the cat sa |
| 6 | 1 | the cat sat |
「끝나는 자리」로 알려줍니다. 오차가 있으면 시작 자리가 하나로 정해지지 않기 때문입니다 — 같은 끝 자리에 대해 길이가 다른 여러 부분이 조건을 만족할 수 있습니다. 「그 언저리」의 굵은 부분은 짐작한 범위입니다.
글자별 마스크 B[c]
| 글자 | 패턴에서 그 글자가 있는 자리 |
|---|---|
| a | 010 |
| c | 001 |
| r | 100 |
비트열은 왼쪽이 윗자리입니다. 패턴에 없는 글자의 마스크는 0이라, 그 글자를 만나면 상태가 통째로 꺼집니다.
상태 비트가 밀려 가는 모습
| 자리 | 글자 | R0 | R1 |
|---|---|---|---|
| 0 | t | 000 | 001 |
| 1 | h | 000 | 001 |
| 2 | e | 000 | 001 |
| 3 | ␣ | 000 | 001 |
| 4 | c | 001 | 011 |
| 5 | a | 010 | 111 |
| 6 | t | 000 | 111 |
| 7 | ␣ | 000 | 001 |
| 8 | s | 000 | 001 |
| 9 | a | 000 | 011 |
| 10 | t | 000 | 001 |
| 11 | ␣ | 000 | 001 |
| 12 | o | 000 | 001 |
| 13 | n | 000 | 001 |
| 14 | ␣ | 000 | 001 |
| 15 | t | 000 | 001 |
| 16 | h | 000 | 001 |
| 17 | e | 000 | 001 |
| 18 | ␣ | 000 | 001 |
| 19 | m | 000 | 001 |
| 20 | a | 000 | 011 |
| 21 | t | 000 | 001 |
R₀은 하나도 틀리지 않은 상태, R₁ 이상은 그만큼 틀려도 되는 상태입니다. 맨 왼쪽 비트가 켜지면 패턴을 끝까지 맞춘 것이라 그 줄을 굵게 표시했습니다. 앞 22글자만 보입니다.
사용 방법
- 1본문과 찾을 말을 넣습니다.
- 2허용할 오차 글자 수를 정합니다. 0이면 정확한 검색입니다.
- 3찾은 자리와 각각 몇 글자 틀렸는지 확인합니다.
- 4글자마다 상태 비트가 어떻게 밀려 가는지 표에서 봅니다.
- 5오차를 하나씩 올려 찾는 자리가 어떻게 늘어나는지 확인합니다.
자주 묻는 질문
패턴의 어느 접두사까지 맞았는지를 정수 하나의 비트로 들고 다니며 문자열을 찾는 방법입니다. 글자 하나를 처리하는 것이 R ← ((R << 1) | 1) & B[c] 한 줄이고, 맨 윗비트가 켜지면 패턴을 찾은 것입니다. Shift-And 또는 Shift-Or라고도 부릅니다.
패턴이 워드 길이 이하면 글자마다 비트 연산 몇 번으로 끝나기 때문입니다. 앞으로 되짚거나 표를 미리 만들 필요가 없어 전체가 O(n)이고, 상수도 아주 작습니다. 대신 패턴이 워드보다 길면 여러 워드로 쪼개야 해서 이 장점이 약해집니다.
패턴과 정확히 같지 않아도 편집거리가 정해진 값 이하면 찾는다는 뜻입니다. 한 글자를 다른 글자로 바꿔 넣거나, 빠뜨리거나, 끼워 넣은 경우가 모두 포함됩니다. 오타가 있는 검색이나 유전자 서열 검색에서 이런 검색이 필요합니다.
상태를 오차 개수만큼 더 둡니다. R_d는 「d 글자까지 틀리면서 맞은 자리」이고, 갱신식이 네 갈래로 늘어납니다 — 맞음, 바꿔 넣기, 빠뜨리기, 끼워 넣기. 이 세 오차가 편집거리의 세 연산에 그대로 대응합니다. 1992년 우와 맨버가 이 방식으로 agrep을 만들었습니다.
KMP는 정확한 검색만 하고, 실패 함수라는 표를 미리 만들어 「어긋났을 때 어디로 돌아갈지」를 씁니다. Bitap은 표 대신 비트를 쓰고 되돌아가지 않으며, 오차를 허용하는 쪽으로 자연스럽게 늘어납니다. 오차가 0이면 두 방법이 같은 답을 냅니다.
상태가 정수 하나에 들어가야 하기 때문입니다. 자바스크립트의 비트 연산은 부호 있는 32비트라 맨 윗비트를 피해 31글자로 제한했습니다. 더 긴 패턴은 상태를 여러 워드로 나눠야 하고, 그러면 「글자마다 상수 시간」이라는 성질이 깨집니다.
전송되지 않습니다. 검색은 모두 브라우저 안에서 이뤄지고, 입력한 본문과 패턴은 이 기기에만 남습니다.
알아두면 좋은 점
- 정답지가 둘입니다. 오차가 0이면 그냥 문자열 찾기와 같은 답이 나와야 하고, 400가지 (본문, 패턴)에서 확인했습니다.
- 오차가 있을 때는 편집거리 표를 채워 「이 자리에서 끝나는 어떤 부분문자열이든 패턴과의 거리가 k 이하인가」를 무식하게 구한 결과와 대조합니다. 알파벳 2·3·4글자, 패턴 2~8글자, 오차 0~4의 조합 2,000가지에서 한 건도 어긋나지 않습니다.
- 개발 중에 이 대조가 실제로 버그를 잡았습니다. 오차 상태를 갱신할 때 밀어 올린 값에 1을 더하는 것을 빠뜨려, 패턴 첫 글자를 바꿔 넣거나 빠뜨려야 맞는 자리를 놓쳤습니다. 무식한 표가 없었다면 그럴듯한 결과를 그대로 내보냈을 것입니다.
- 패턴이 25~31글자로 길어져도 맞는지 따로 검사합니다. 워드 경계 언저리가 이런 구현에서 잘 깨지는 자리입니다.
- k를 키우면 찾는 자리가 늘거나 같은 것, 글자마다 정확히 (3 + 6k)번의 연산만 하는 것도 검사값으로 고정했습니다.
- 바꿔 넣기·빠뜨리기·끼워 넣기 세 가지를 각각 따로 검사합니다. 셋 중 하나만 처리해도 통과하는 검사가 되지 않게 한 것입니다.
- 패턴은 31글자, 본문은 5,000글자, 오차는 8까지 다룹니다.
- 찾은 자리는 「끝나는 자리」로 알려줍니다. 오차가 있으면 시작 자리가 하나로 정해지지 않기 때문입니다 — 같은 끝 자리에 대해 길이가 다른 여러 부분문자열이 조건을 만족할 수 있습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.