자바 민감 어 필터 실례 실현

민감 한 단어,문자 여과 은 한 사이트 에서 없어 서 는 안 될 기능 으로 어떻게 좋 고 효율 적 인 여과 알고리즘 을 설계 하 는 지 매우 필요 하 다.얼마 전에 제 친구(곧 졸업 하고 프로 그래 밍 을 접 한 지 얼마 되 지 않 았 습 니 다)가 문자 가 걸 러 지 는 것 을 보 여 달라 고 했 습 니 다.검색 효율 이 매우 느리다 고 했 습 니 다.프로그램 을 가 져 와 보 니 전체 과정 은 다음 과 같 습 니 다.민감 한 단어 라 이브 러 리 를 읽 고 HashSet 집합 에서 페이지 업로드 문 자 를 가 져 와 일치 합 니 다.나 는 이 과정 이 틀림없이 매우 느 릴 것 이 라 고 생각 했다.접촉 하지 않 은 사람 에 게 도 이것 밖 에 생각 나 지 않 는 다 고 생각 합 니 다.더 높 은 점 은 정규 표현 식 입 니 다.그러나 안 타 깝 게 도 이 두 가지 방법 은 모두 불가능 하 다.물론 저 는 그 알고리즘 이 문 제 를 해결 할 수 있다 는 것 을 의식 하지 못 했 습 니 다.하지만 구 글 은 알 고 있 습 니 다!
 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)세 가지 방법.
민감 하 다
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.

좋은 웹페이지 즐겨찾기