algorithm 알고리즘 Strings 문자열 Regular Expression Matching 정규 표현식 매칭

[Algorithm] Strings - Regular Expression Matching

문자열 정규 표현식 매칭

Posted by lim.Chuck on October 1, 2024

Rabin-Karp?

Rabin-Karp 알고리즘은 문자열에서 특정 패턴을 찾는 데 사용되는 효율적인 해시 기반 문자열 검색 알고리즘입니다. 이 알고리즘의 핵심은 해시 함수를 이용해 텍스트와 패턴의 해시 값을 계산하고, 이를 비교하여 패턴을 찾는 방식입니다.

동작 방식:

  1. 패턴과 텍스트의 첫 번째 부분의 해시 값을 계산합니다.
  2. 이후 텍스트의 다음 부분을 한 글자씩 이동하면서 해시 값을 업데이트하고, 패턴의 해시 값과 비교합니다.
  3. 해시 값이 일치하는 경우, 문자열을 실제로 비교하여 패턴이 맞는지 확인합니다.
  4. 해시 충돌이 발생할 수 있으므로, 해시 값이 일치할 때 실제로 문자열을 비교하는 단계가 필요합니다.

사용 사례:

  • 문자열 검색: 긴 텍스트에서 짧은 패턴을 효율적으로 검색하는 데 사용됩니다.
  • Plagiarism Detection(표절 검사): 해시 값을 사용해 두 문서가 비슷한지 빠르게 확인할 수 있습니다.
  • DNA 서열 분석: 유전자 서열에서 특정 패턴을 찾는 데 사용될 수 있습니다.

JavaScript 예제 코드: Rabin-Karp 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

function rabinKarp(text, pattern) {
  const d = 256; // 알파벳 수
  const q = 101; // 소수 (해시 충돌을 줄이기 위해 사용)
  const m = pattern.length;
  const n = text.length;
  let p = 0; // 패턴의 해시 값
  let t = 0; // 텍스트의 해시 값
  let h = 1;

  // h의 값을 계산, h = pow(d, m-1) % q
  for (let i = 0; i < m - 1; i++) {
    h = (h * d) % q;
  }

  // 패턴과 텍스트 첫 번째 윈도우의 해시 값을 계산
  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % q;
    t = (d * t + text.charCodeAt(i)) % q;
  }

  // 텍스트에서 패턴을 검색
  for (let i = 0; i <= n - m; i++) {
    // 해시 값이 같으면 실제 문자열을 비교
    if (p === t) {
      let j = 0;
      for (j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          break;
        }
      }
      if (j === m) {
        console.log(`Pattern found at index ${i}`);
      }
    }

    // 다음 윈도우의 해시 값을 계산
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (t < 0) {
        t = t + q;
      }
    }
  }
}

// 사용 예시
const text = "GEEKS FOR GEEKS";
const pattern = "GEEK";
rabinKarp(text, pattern); // Output: Pattern found at index 0, 10

설명:

  • rabinKarp 함수는 텍스트에서 패턴을 검색하며, 각 윈도우의 해시 값을 계산하고 비교하여 일치하는 패턴을 찾습니다.
  • 해시 충돌이 발생할 수 있으므로 해시 값이 동일할 때는 실제 문자열 비교를 수행합니다.

Rust 예제 코드: Rabin-Karp 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

fn rabin_karp(text: &str, pattern: &str) {
    let d: i32 = 256;
    let q: i32 = 101;
    let m = pattern.len();
    let n = text.len();
    let mut p: i32 = 0; // 패턴의 해시 값
    let mut t: i32 = 0; // 텍스트의 해시 값
    let mut h: i32 = 1;

    // h = pow(d, m-1) % q 계산
    for _ in 0..(m-1) {
        h = (h * d) % q;
    }

    // 패턴과 텍스트의 첫 윈도우 해시 값 계산
    for i in 0..m {
        p = (d * p + pattern.as_bytes()[i] as i32) % q;
        t = (d * t + text.as_bytes()[i] as i32) % q;
    }

    // 텍스트에서 패턴을 검색
    for i in 0..=(n - m) {
        // 해시 값이 일치하면 실제로 문자열을 비교
        if p == t {
            if &text[i..i+m] == pattern {
                println!("Pattern found at index {}", i);
            }
        }

        // 다음 윈도우의 해시 값을 계산
        if i < n - m {
            t = (d * (t - (text.as_bytes()[i] as i32 * h)) + text.as_bytes()[i + m] as i32) % q;
            if t < 0 {
                t = t + q;
            }
        }
    }
}

fn main() {
    let text = "GEEKS FOR GEEKS";
    let pattern = "GEEK";
    rabin_karp(text, pattern); // Output: Pattern found at index 0, 10
}

설명:

  • Rust 코드는 JavaScript 코드와 동일한 논리를 따르며, 텍스트와 패턴의 해시 값을 계산하여 패턴을 검색합니다.
  • 해시 값이 동일할 때는 실제로 패턴과 텍스트를 비교하여 패턴이 일치하는지 확인합니다.

요약:

Rabin-Karp 알고리즘은 해시 함수를 사용하여 텍스트 내에서 특정 패턴을 찾는 효율적인 방법입니다. 특히, 여러 패턴을 검색하거나 매우 긴 텍스트에서 짧은 패턴을 찾는 경우 유용하게 사용됩니다.

Regular Expression Matching Explanation?

Regular Expression (Regex) is a powerful tool used for searching, validating, or transforming text based on specific patterns. Regular expression matching involves determining whether a given string matches a defined pattern. This is widely used in tasks that involve text processing, such as data validation, text search, and manipulation.

Use Cases:

  • Data Validation: Commonly used to check input formats, such as emails, phone numbers, or zip codes.
  • Text Search and Replace: Useful for finding and replacing specific patterns in large text files.
  • Log Analysis: Extracting important information from log files based on patterns.

JavaScript Example Code

1
2
3
4
5
6
7
8
9
10
11
12
13

function isMatch(s, pattern) {
  const regex = new RegExp(`^${pattern}$`);
  return regex.test(s);
}

// Usage Example
const s1 = "abc";
const pattern1 = "a.c"; // '.' matches any single character
console.log(isMatch(s1, pattern1)); // true

const s2 = "abcd";
const pattern2 = "a.*d"; // '.*' matches any sequence of characters
console.log(isMatch(s2, pattern2)); // true

Explanation:

  • This JavaScript function checks if the string s matches the regular expression pattern.
  • new RegExp() dynamically creates a regular expression, and the test() method checks if the string matches the pattern.
  • ^ ensures the match starts at the beginning of the string, and $ ensures the match ends at the last character.

Rust Example Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

extern crate regex;
use regex::Regex;

fn is_match(s: &str, pattern: &str) -> bool {
    let regex = Regex::new(&format!("^{}$", pattern)).unwrap();
    regex.is_match(s)
}

fn main() {
    let s1 = "abc";
    let pattern1 = "a.c";  // '.' matches any single character
    println!("{}", is_match(s1, pattern1));  // true

    let s2 = "abcd";
    let pattern2 = "a.*d";  // '.*' matches any sequence of characters
    println!("{}", is_match(s2, pattern2));  // true
}

Explanation:

  • The Rust code uses the external regex crate to handle regular expressions.
  • Regex::new() creates the regular expression, and the is_match() method checks if the string matches the pattern.
  • Similar to JavaScript, ^ and $ are used to ensure that the entire string matches the pattern.

Summary:

Regular expression matching is widely used in various text processing tasks such as data validation, text search, and transformation. Both JavaScript and Rust provide efficient ways to handle regular expressions, using the RegExp object in JavaScript and the regex crate in Rust.

FEATURED TAGS
git 알고리즘 algorithm js 기초 js 기초 문법 js 문법 자료구조 Data Structure Graphs React 그래프 러스트 rust 집합 Sets front 수학 정렬 Math Sorting 간단예제 문자열 Strings github AWS 이벤트 버블링 이벤트 캡처링 탐색 LLM MCP Searches 컴파일러 트리 AI Cloud Front Cursor MCP 사용법 bubbling capturing s3 개발자도구 광고 구글 자동색인 깃허브 광고 라이브러리 러스트 설치 리엑트 버킷 비교 사이트맵 아마존 예제 웹 접근성 이미지 업로드 최장 공통 부분수열 캐시 텍스트 프레임워크 AI통합 API Adsense Claude Compiler SQL SWC Speedy Web Compiler Trees js 변수 js 생성자함수 npm nuxt pipeline project management robots rust 구축 rust setting rust setup text utterances
FRIENDS