자바 민감 어 필터 실례 실현
DFA 소개
문자 필 터 를 구현 하 는 알고리즘 중 DFA 는 유일 하 게 비교적 좋 은 구현 알고리즘 이다.DFA 는 Deterministic Finite Automation 입 니 다.즉,가난 한 자동 기 를 확인 하 는 것 입 니 다.이벤트 와 현재 state 를 통 해 다음 state,즉 이벤트+state=nextstate 를 얻 는 것 입 니 다.다음 그림 은 그 상태의 전환 을 보 여 준다
이 그림 에서 대문자(S,U,V,Q)는 모두 상태 이 고 소문 자 a,b 는 동작 이다.위의 그림 을 통 해 우 리 는 다음 과 같은 관 계 를 볼 수 있다.
a b b
S -----> U S -----> V U -----> V
민감 한 단 어 를 걸 러 내 는 알고리즘 에서 우 리 는 연산 을 줄 여야 하 는데 DFA 는 DFA 알고리즘 에서 계산 이 거의 없고 어떤 것 은 상태의 전환 일 뿐이다.
자바 DFA 알고리즘 구현 민감 어 필터 링
자바 에서 민감 어 필 터 를 실현 하 는 관건 은 DFA 알고리즘 의 실현 이다.우선 우 리 는 위의 그림 에 대해 분석 을 진행한다.이 과정 에서 우 리 는 아래 의 이런 구조 가 더욱 명확 해 질 것 이 라 고 생각한다.
동시에 여 기 는 상태 전환 이 없고 동작 이 없 으 며 어떤 것 은 Query(찾기)일 뿐 입 니 다.S query U,V,U query V,P,V query U P 를 통 해이러한 변 화 를 통 해 우 리 는 상태의 전환 을 자바 집합 을 사용 한 검색 으로 바 꿀 수 있다.
물론 우리 의 민감 한 단어 창고 에 가입 하면 다음 과 같은 몇 가지 민감 한 단어 가 존재 한다.일본 인,일본놈,모.택.동.그렇다면 나 는 어떤 구 조 를 구축 해 야 할 까?
먼저:query 일--->{본},query 본--->{사람,놈},query 사람--->{null},query 귀신--->{자}.다음 과 같은 구조:
다음은 이 그림 을 확장 하고 있 습 니 다.
이렇게 해서 우 리 는 우리 의 민감 한 단어 라 이브 러 리 를 하나의 트 리 와 유사 하 게 구축 했다.그러면 우 리 는 한 단어 가 민감 한 단어 인지 아 닌 지 를 판단 할 때 검색 의 일치 범 위 를 크게 줄 였 다.예 를 들 어 우 리 는 일본 인 을 판단 해 야 한다.첫 글자 에 따라 우 리 는 검색 해 야 할 나무 가 그 나무 라 는 것 을 확인 한 다음 에 이 나무 에서 검색 할 수 있다.
하지만 민감 한 단어 가 끝났다 는 것 을 어떻게 판단 할 것 인가?표지 위 치 를 이용 하여 판단 하 다.
그래서 이 관건 은 이런 민감 한 단어 나 무 를 어떻게 구축 하 느 냐 하 는 것 이다.다음은 자바 의 HashMap 을 예 로 들 어 DFA 알고리즘 을 실현 합 니 다.구체 적 인 과정 은 다음 과 같다.
일본놈
1.hashMap 에서'일'이 hashMap 에 존재 하 는 지 확인 하고 존재 하지 않 으 면'일'로 시작 하 는 민감 한 단어 가 존재 하지 않 는 다 는 것 을 증명 한다.그러면 우 리 는 이런 나 무 를 직접 구축한다.뛰다
2.hashMap 에서 찾 으 면'일'로 시작 하 는 민감 한 단어 가 존재 한 다 는 것 을 나타 내 고 hashMap=hashMap.get('일')을 설정 하고 1 로 넘 어가'본','사람'과 순서대로 일치 합 니 다.
3.이 글자 가 이 단어의 마지막 글자 인지 판단 한다.민감 한 단어 가 끝 났 음 을 나타 내 면 표지 위치 isEnd=1 을 설정 하고 그렇지 않 으 면 표지 위치 isEnd=0 을 설정 합 니 다
프로그램 구현 은 다음 과 같 습 니 다.
/**
* , HashSet , DFA :<br>
* = {
* isEnd = 0
* = {<br>
* isEnd = 1
* = {isEnd = 0
* = {isEnd = 1}
* }
* = {
* isEnd = 0
* = {
* isEnd = 1
* }
* } [ 0-9]
* }
* }
* = {
* isEnd = 0
* = {
* isEnd = 0
* = {
* isEnd = 0
* = {
* isEnd = 1
* }
* }
* }
* }
* @author chenming
* @date 2014 4 20 3:04:20
* @param keyWordSet
* @version 0
*/
@SuppressWarnings({ "rawtypes", "unchecked" })
private void addSensitiveWordToHashMap(Set<String> keyWordSet) {
sensitiveWordMap = new HashMap(keyWordSetsize()); // ,
String key = null;
Map nowMap = null;
Map<String, String> newWorMap = null;
// keyWordSet
Iterator<String> iterator = keyWordSetiterator();
while(iteratorhasNext()){
key = iteratornext(); //
nowMap = sensitiveWordMap;
for(int i = 0 ; i < keylength() ; i++){
char keyChar = keycharAt(i); // char
Object wordMap = nowMapget(keyChar); //
if(wordMap != null){ // key,
nowMap = (Map) wordMap;
}
else{ // , map, isEnd 0,
newWorMap = new HashMap<String,String>();
newWorMapput("isEnd", "0"); //
nowMapput(keyChar, newWorMap);
nowMap = newWorMap;
}
if(i == keylength() - 1){
nowMapput("isEnd", "1"); //
}
}
}
}
실행 할 수 있 는 hashMap 구 조 는 다음 과 같 습 니 다.{5={별={빨간색={isEnd=0,깃발={isEnd=1},isEnd=0},isEnd=0},중={isEnd=0,국={isEnd=0,인={isEnd=1},남={isEnd=0,인={isEnd=1}}}}}}}}
민감 한 어고 가 우리 에 게 간단 한 방법 으로 이 루어 졌 다 면 어떻게 검색 을 실현 할 수 있 습 니까?검색 과정 은 hashMap 의 get 실현 일 뿐만 아니 라 이 단 어 를 찾 으 면 민감 한 단어 임 을 증명 합 니 다.그렇지 않 으 면 민감 한 단어 가 아 닙 니 다.과정 은 다음 과 같다.만약 우리 가'중국인 민 만세'와 일치한다 면.
1.첫 번 째 글자'중'은 hashMap 에서 찾 을 수 있 습 니 다.새로운 맵 을 가 져 옵 니 다=hashMap.get(").
2.map==null 이면 민감 한 단어 가 아 닙 니 다.아니면 3 까지.
3.map 의 isEnd 를 가 져 오고 isEnd 가 1 인지 여 부 를 통 해 이 단어 가 마지막 인지 여 부 를 판단 합 니 다.만약 isEnd==1 이 이 단 어 를 민감 한 단어 로 표시 한다 면,그렇지 않 으 면 1 로 건 너 뜁 니 다.
이 절 차 를 통 해 우 리 는'중국인 민'을 민감 한 단어 로 판단 할 수 있 지만 우리 가'중국 여자'를 입력 하면 민감 한 단어 가 아니다.
/**
* , :<br>
* @author chenming
* @date 2014 4 20 4:31:03
* @param txt
* @param beginIndex
* @param matchType
* @return, , , 0
* @version 0
*/
@SuppressWarnings({ "rawtypes"})
public int CheckSensitiveWord(String txt,int beginIndex,int matchType){
boolean flag = false; // : 1
int matchFlag = 0; // 0
char word = 0;
Map nowMap = sensitiveWordMap;
for(int i = beginIndex; i < txtlength() ; i++){
word = txtcharAt(i);
nowMap = (Map) nowMapget(word); // key
if(nowMap != null){ // ,
matchFlag++; // key, +1
if("1"equals(nowMapget("isEnd"))){ // , ,
flag = true; // true
if(SensitivewordFilterminMatchTYpe == matchType){ // , ,
break;
}
}
}
else{ // ,
break;
}
}
if(matchFlag < 2 && !flag){
matchFlag = 0;
}
return matchFlag;
}
글 말미 에 나 는 자바 를 이용 하여 민감 한 단 어 를 걸 러 내 는 파일 다운 로드 를 제공 했다.다음은 이 알고리즘 의 효율 과 신뢰성 을 증명 하 는 테스트 클래스 입 니 다.
public static void main(String[] args) {
SensitivewordFilter filter = new SensitivewordFilter();
Systemoutprintln(" :" + filtersensitiveWordMapsize());
String string = " , 。"
+ " , ,"
+ " , 。";
Systemoutprintln(" :" + stringlength());
long beginTime = SystemcurrentTimeMillis();
Set<String> set = filtergetSensitiveWord(string, 1);
long endTime = SystemcurrentTimeMillis();
Systemoutprintln(" :" + setsize() + "。 :" + set);
Systemoutprintln(" :" + (endTime - beginTime));
}
실행 결과:위의 결 과 를 통 해 알 수 있 듯 이 민감 한 단어 고 는 771 개 이 고 검 측 문장의 길 이 는 184 글자 이 며 6 개의 민감 한 단 어 를 찾 아 냈 다.총 1 밀리초 걸 립 니 다.보 이 는 속 도 는 여전히 매우 가관이다.
다음은 두 개의 문 서 를 다운로드 합 니 다.
Desktop.rar(http://xiazai.jb51.net/201611/yuanma/Desktop_jb51.rar)에는 두 개의 자바 파일 이 포함 되 어 있 습 니 다.하 나 는 민감 한 단어 라 이브 러 리(SensitiveWordInit)를 읽 는 것 입 니 다.하 나 는 민감 한 단어 도구 류(SensitiveWordFilter)입 니 다.하 나 는 민감 한 단어 가 있 는 지 판단 하 는 것(isContaintSensitiveWord(String txt,int matchType),민감 한 단어 가 져 오기(getSensitiveWord(String txt,int matchType),민감 한 단어 대체(replace SensitiveWord(String txt,int match Type,String replace Char)세 가지 방법.
민감 하 다
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.