1 |
1
검출하고자 하는 적어도 하나의 패턴 각각에 대한 다수의 하위 문자열과 다수의 하위 문자열 각각으로부터 대응하는 패턴이 나타날 확률을 계산하는 확률 유한 오토마타를 생성하고, 상기 확률 유한 오토마타를 상기 다수의 하위 문자열 각각에 대한 확률을 누적 합으로 계산하기 위한 가중 오토마타로 모델링하는 가중 오토마타 모델링부; 입력되는 텍스트에서 하위 문자열 패턴 매칭이 수행될 문자열을 지정하기 위한 윈도우를 설정하는 윈도우 설정부; 및 상기 윈도우에 의해 지정된 문자열에서 기지정된 위치의 문자로부터 연속하는 문자들에 대한 하위 문자열로부터 패턴이 나타날 확률을 상기 가중 오토마타를 이용하여 누적 합으로 계산하고, 상기 누적 합을 기지정된 임계값과 비교하여, 상기 텍스트 내에서 상기 적어도 하나의 패턴을 검출하기 위한 역추적 여부를 판정하는 패턴 확률 판정부; 를 포함하고, 상기 가중 오토마타 모델링부는 상기 적어도 하나의 패턴 각각에 대한 다수의 하위 문자열과 다수의 하위 문자열 각각으로부터 대응하는 패턴이 나타날 확률이 미리 저장되는 패턴 저장부; 상기 패턴 저장부에 저장된 상기 다수의 하위 문자열과 상기 다수의 하위 문자열 각각에 대한 확률에 따라 상기 확률 유한 오토마타를 생성하는 확률 유한 오토마타 생성부; 및 상기 확률 유한 오토마타에 기지정된 초기 상태와 λ 전이 조건 및 가중 셀프 루프를 추가하여 상기 가중 오토마타로 변환하는 가중 오토마타 변환부; 를 포함하는 실시간 확률 패턴 매칭 장치
|
2 |
2
삭제
|
3 |
3
제1 항에 있어서, 상기 가중 오토마타 변환부는 상기 확률 유한 오토마타에 시작 확률이 1이고 종료 확률이 0인 별도의 초기 상태를 추가하고, 추가된 상기 초기 상태로부터 상기 확률 유한 오토마타에서 시작 확률이 0이 아닌 모든 상태로 전이하기 위한 조건인 λ 전이 조건을 추가하며, 상기 초기 상태에 상기 적어도 하나의 패턴 각각에 대한 다수의 하위 문자열에 대해 1의 가중 확률값을 갖는 전이 조건인 가중 셀프 루프를 추가하여 상기 가중 오토마타로 변환하는 실시간 확률 패턴 매칭 장치
|
4 |
4
제3 항에 있어서, 상기 가중 오토마타 변환부는 상기 λ 전이 조건의 확률을 상기 확률 유한 오토마타에서 시작 확률이 0이 아닌 모든 상태 각각의 시작 확률로 설정하고, 상기 확률 유한 오토마타에서 시작 확률이 0이 아닌 모든 상태 각각의 시작 확률을 0으로 변경하는 실시간 확률 패턴 매칭 장치
|
5 |
5
제1 항에 있어서, 상기 패턴 확률 판정부는 상기 누적 합이 상기 임계값 이상이면, 상기 다수의 하위 문자열 각각의 확률을 상기 임계값과 비교하고, 상기 다수의 하위 문자열 각각의 확률 중 적어도 하나가 상기 임계값 이상이면, 상기 임계값 이상인 하위 문자열을 역추적을 위해 출력하는 실시간 확률 패턴 매칭 장치
|
6 |
6
제5 항에 있어서, 상기 윈도우 설정부는 상기 누적 합이 상기 임계값 미만이거나, 상기 다수의 하위 문자열 각각의 확률이 상기 임계값 미만이면, 상기 텍스트에서 상기 윈도우의 위치를 기지정된 방향으로 이동시키는 실시간 확률 패턴 매칭 장치
|
7 |
7
제5 항에 있어서, 상기 실시간 확률 패턴 매칭 장치는 상기 패턴 확률 판정부에서 상기 하위 문자열이 출력되면, 상기 텍스트에서 상기 윈도우의 현재 위치로부터 상기 하위 문자열에 대응하는 패턴을 역추적하는 역추적부; 를 더 포함하는 실시간 확률 패턴 매칭 장치
|
8 |
8
제7 항에 있어서, 상기 역추적부는 상기 텍스트에서 상기 하위 문자열에 대응하는 패턴이 역추적되면, 상기 텍스트에서 역추적된 패턴의 시작 위치 및 종료 위치를 출력하는 실시간 확률 패턴 매칭 장치
|
9 |
9
검출하고자 하는 적어도 하나의 패턴 각각에 대한 다수의 하위 문자열과 다수의 하위 문자열 각각으로부터 대응하는 패턴이 나타날 확률을 계산하는 확률 유한 오토마타를 생성하는 단계; 상기 확률 유한 오토마타를 상기 다수의 하위 문자열 각각에 대한 확률을 누적 합으로 계산하기 위한 가중 오토마타로 모델링하는 단계; 입력되는 텍스트에서 하위 문자열 패턴 매칭이 수행될 문자열을 지정하기 위한 윈도우를 설정하는 단계; 상기 윈도우에 의해 지정된 문자열에서 기지정된 위치의 문자로부터 연속하는 문자들에 대한 하위 문자열로부터 패턴이 나타날 확률을 상기 가중 오토마타를 이용하여 누적 합으로 계산하는 단계; 및 상기 누적 합을 기지정된 임계값과 비교하여, 상기 텍스트 내에서 상기 적어도 하나의 패턴을 검출하기 위한 역추적 여부를 판정하는 단계; 를 포함하고, 상기 확률 유한 오토마타를 생성하는 단계는 미리 저장된 상기 적어도 하나의 패턴 각각에 대한 다수의 하위 문자열과 다수의 하위 문자열 각각으로부터 대응하는 패턴이 나타날 확률에 따라 상기 확률 유한 오토마타를 생성하는 실시간 확률 패턴 매칭 방법
|
10 |
10
삭제
|
11 |
11
제9 항에 있어서, 상기 가중 오토마타로 모델링하는 단계는 상기 확률 유한 오토마타에 시작 확률이 1이고 종료 확률이 0인 별도의 초기 상태를 추가하는 단계; 상기 초기 상태에 상기 적어도 하나의 패턴 각각에 대한 다수의 하위 문자열에 대해 1의 가중 확률값을 갖는 전이 조건인 가중 셀프 루프를 추가하는 단계; 추가된 상기 초기 상태로부터 상기 확률 유한 오토마타에서 시작 확률이 0이 아닌 모든 상태로 전이하기 위한 조건인 λ 전이 조건을 추가하고, 상기 λ 전이 조건의 확률을 상기 확률 유한 오토마타에서 시작 확률이 0이 아닌 모든 상태 각각의 시작 확률로 설정하는 단계; 및상기 확률 유한 오토마타에서 시작 확률이 0이 아닌 모든 상태 각각의 시작 확률을 0으로 변경하는 단계; 를 포함하는 실시간 확률 패턴 매칭 방법
|
12 |
12
제9 항에 있어서, 상기 역추적 여부를 판정하는 단계는 상기 누적 합이 상기 임계값 이상이면, 상기 다수의 하위 문자열 각각의 확률을 상기 임계값과 비교하는 단계; 상기 다수의 하위 문자열 각각의 확률 중 적어도 하나가 상기 임계값 이상이면, 역추적을 위해 상기 임계값 이상인 하위 문자열을 출력하는 단계; 및상기 누적 합이 상기 임계값 미만이거나, 상기 다수의 하위 문자열 각각의 확률이 상기 임계값 미만이면, 상기 텍스트에서 상기 윈도우의 위치를 기지정된 방향으로 이동시키는 단계; 를 더 포함하는 실시간 확률 패턴 매칭 방법
|
13 |
13
제12 항에 있어서, 상기 실시간 확률 패턴 매칭 방법은 역추적을 위한 상기 하위 문자열이 출력되면, 상기 텍스트에서 상기 윈도우의 현재 위치로부터 상기 하위 문자열에 대응하는 패턴을 역추적하는 단계; 를 더 포함하는 실시간 확률 패턴 매칭 방법
|
14 |
14
제13 항에 있어서, 상기 역추적하는 단계는 상기 텍스트에서 상기 하위 문자열에 대응하는 패턴이 역추적되면, 상기 텍스트에서 역추적된 패턴의 시작 위치 및 종료 위치를 출력하는 실시간 확률 패턴 매칭 방법
|