데이터 구조 시리즈 - 트 리
트 리 구조
Trie 의 핵심 사상 은 공간 교환 시간 이다. 문자열 의 공공 접 두 사 를 이용 하여 조회 시간의 비용 을 낮 추어 효율 을 높이 는 목적 을 달성 하 는 것 이다.
예 를 들 어 tea, ten, to, in, inn, int 라 는 단 어 를 하나의 Trie 나무 로 구축 하고 구체 적 인 Tried 나무의 구 조 를 살 펴 보 자.
그림: 트 리 구조
그림 에서 트 리 의 일부 특성 을 볼 수 있다.
트 리 구현
Trie 트 리 의 삽입, 삭제, 찾기 동작 은 모두 같 습 니 다. 트 리 를 간단하게 한 번 옮 겨 다 니 면 됩 니 다. 시간 복잡 도: O (n) (n 은 문자열 의 길이).Tried 트 리 의 실현 은 배열 과 링크 두 가지 방식 을 사용 할 수 있 습 니 다.
다음은 가장 간단 한 트 리 트 리 의 실현 으로 배열 방식 을 사용한다.
/**
*
* Trie ， Trie ，
*
*
* @author Vicky
* @email [email protected]
* @2015 11 23
*
*/
public class Trie {
protected TrieNode root = new TrieNode('a');// TrieTree
/**
*
*
* @param word
*/
public void insertWord(String word) {
TrieNode index = this.root;
for (char c : word.toLowerCase().toCharArray()) {
index = index.addChild(c);
}
return;
}
/**
* TrieTree
*/
private class TrieNode {
/** */
private final char nodeChar;//
/** TrieTree */
private TrieNode[] childNodes = null;
public TrieNode(char nodeChar) {
super();
this.nodeChar = nodeChar;
}
public TrieNode addChild(char ch) {
int index = ch - 'a';
if (null == childNodes) {
this.childNodes = new TrieNode[26];
}
if (null == childNodes[index]) {
childNodes[index] = new TrieNode(ch);
}
return childNodes[index];
}
@Override
public String toString() {
return "TrieNode [nodeChar=" + nodeChar + "]";
}
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insertWord("Vicky");
}
}Trie 트 리 응용
Trie 트 리 의 응용 은 주로 문자열 처리 에 집중 되 어 있 습 니 다.(1) 문자열 검색
(2) 최 장 공공 접두사
다음은 트 리 트 리 의 응용 에 대해 상대 적 으로 간단 하고 대표 적 인 사례 를 선택 하 겠 습 니 다. 한 단어 에서 'vi' 로 시작 하 는 모든 문자열 을 찾 고 'Vicky' 가 나 타 났 는 지 확인 하 겠 습 니 다.(우 리 는 26 글자 만 저장 하기 때문에 대소 문 자 를 구분 하지 않 고 단어 가 아 닌 문 자 를 지원 하지 않 습 니 다.)
인터넷 에서 다음 단어 표를 다운로드 하고 단어 표 에 따라 트 리 트 리 를 구축 하고 찾 을 수 있 습 니 다. 단어 표 는https://github.com/dwyl/english-words다운 로드 를 진행 하 다.
package com.vicky.datastructure.tree.trie;
/**
*
* Trie
*
*
* @author Vicky
* @email [email protected]
* @2015 11 23
*
*/
public class PrefixTrie {
private TrieNode root = new TrieNode('a');// TrieTree
/**
*
*
* @param word
*/
public void insertWord(String word) {
TrieNode index = this.root;
for (char c : word.toLowerCase().toCharArray()) {
index = index.addChild(c);
index.addPrefixCount();
}
index.addCount();
return;
}
/**
*
*
* @param word
* @return
*/
public boolean selectWord(String word) {
TrieNode index = this.root;
for (char c : word.toLowerCase().toCharArray()) {
index = index.getChild(c);
if (null == index) {
return false;
}
}
return index.getCount() > 0;
}
/**
*
*
* @param prefix
* @return
*/
public int selectPrefixCount(String prefix) {
TrieNode index = this.root;
for (char c : prefix.toLowerCase().toCharArray()) {
index = index.getChild(c);
if (null == index) {
return 0;
}
}
return index.getPrefixCount();
}
/**
* TrieTree
*/
private class TrieNode {
/** */
private final char nodeChar;//
/** TrieTree */
private TrieNode[] childNodes = null;
private int count = 0;// ，
private int prefixCount = 0;// ，
public TrieNode(char nodeChar) {
super();
this.nodeChar = nodeChar;
}
public TrieNode addChild(char ch) {
int index = ch - 'a';
if (null == childNodes) {
this.childNodes = new TrieNode[26];
}
if (null == childNodes[index]) {
childNodes[index] = new TrieNode(ch);
}
return childNodes[index];
}
public TrieNode getChild(char ch) {
int index = ch - 'a';
if (null == childNodes || null == childNodes[index]) {
return null;
}
return childNodes[index];
}
public void addCount() {
this.count++;
}
public int getCount() {
return this.count;
}
public void addPrefixCount() {
this.prefixCount++;
}
public int getPrefixCount() {
return this.prefixCount;
}
@Override
public String toString() {
return "TrieNode [nodeChar=" + nodeChar + "]";
}
}
}
package com.vicky.datastructure.tree.trie;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Pattern;
import org.junit.Before;
import org.junit.Test;
public class TrieUsedTest {
private PrefixTrie trie;
@Before
public void before() throws IOException {
Pattern pattern = Pattern.compile("[a-zA-Z]+");
// ， TriedTree
InputStreamReader read = new InputStreamReader(this.getClass().getResourceAsStream("words.txt"));
BufferedReader reader = new BufferedReader(read);
trie = new PrefixTrie();
String line = null;
while (null != (line = reader.readLine())) {
line = line.trim();
if (!pattern.matcher(line).matches()) {// ， “-”
continue;
}
trie.insertWord(line);
}
}
/**
* TriedTree
*/
@Test
public void searchPrefixWords() {
String prefix = "vi";
System.out.println(trie.selectPrefixCount(prefix));
System.out.println(trie.selectWord("Vicky"));
}
}
코드 에서 정확 한 검색 과 접 두 사 를 찾 는 두 가지 방식 을 지원 하기 위해 저 희 는 TrieNode 를 수정 하여
private int count = 0;private int prefixCount = 0; 두 개의 변 수 를 추 가 했 습 니 다. 각각 단어 가 나타 나 는 횟수 와 접두사 가 나타 나 는 횟수 를 저장 하 는 데 사 용 됩 니 다.테스트 결 과 는 텍스트 편집 기 를 사용 하여 대 비 를 찾 을 수 있 습 니 다.트 리 트 리 의 응용 장면 에 대해 서 는 참고 글 1 을 읽 을 수 있 습 니 다.
참고 문장
데이터 구조의 트 리 트 리 는 트 리 (사전 트 리) 에서 접미사 트 리 (10.28 수정) 까지 6 일 동안 트 리 구 조 를 통식 합 니 다. 5 일 째 트 리 입 니 다.
저의 개인 블 로그 에 오신 것 을 환영 합 니 다. 더 많은 즐거움 을 찾 으 세 요 ~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
