이 글은 주로 JavaScript trie 단어 검색 트리의 예를 소개합니다. trie의 개념과 구현에 대해 자세히 소개합니다. 관심 있는 친구들이 참고할 수 있기를 바랍니다.
소개
접두어, 단어 검색 트리, 사전 트리라고도 알려진 트라이 트리(단어 검색에서 유래)는 해시 트리의 변형인 트리 구조이며 빠른 검색 다중 트리에 사용됩니다. 구조.
장점은 불필요한 문자열 비교를 최소화하고 해시 테이블보다 쿼리 효율성이 높다는 것입니다.
Trie의 핵심 아이디어는 공간과 시간을 교환하는 것입니다. 문자열의 공통 접두사를 사용하면 쿼리 시간 오버헤드를 줄여 효율성을 높일 수 있습니다.
Trie 트리에도 단점이 있습니다. 문자와 숫자만 처리한다고 가정하면 각 노드에는 최소 52+10개의 하위 노드가 있습니다. 메모리를 절약하기 위해 연결 목록이나 배열을 사용할 수 있습니다. JS 배열은 동적이며 최적화 기능이 내장되어 있으므로 JS에서는 배열을 직접 사용합니다.
기본 속성
루트 노드에는 문자가 포함되지 않으며 루트 노드를 제외한 모든 하위 노드에는 루트 노드에서 특정 노드까지 문자
가 포함됩니다. 경로를 통과하는 문자는 연결되어 있는데, 이는 노드에 해당하는 문자열입니다.
각 노드의 모든 하위 노드에는 서로 다른 문자가 포함됩니다
프로그램 구현
// by 司徒正美 class Trie { constructor() { this.root = new TrieNode(); } isValid(str) { return /^[a-z1-9]+$/i.test(str); } insert(word) { // addWord if (this.isValid(word)) { var cur = this.root; for (var i = 0; i <p></p><p>집중해 보겠습니다. TrieNode 및 Trie의 삽입 메소드입니다. 사전 트리는 주로 단어 빈도 통계에 사용되므로 numPass, numEnd를 포함한 많은 노드 속성을 갖지만 매우 중요한 속성을 갖습니다. </p><p>insert 메소드는 무거운 단어를 삽입하는 데 사용됩니다. 시작하기 전에 해당 단어가 적합한지, 특수 문자와 공백이 나타날 수 없는지 확인해야 합니다. 삽입 시 캐릭터가 분할되어 각 노드에 배치됩니다. numPass는 노드가 전달될 때마다 수정되어야 합니다. </p><p>최적화<br></p><p>이제 각 방법에는 c=-48이라는 연산이 있습니다. 사실 숫자, 대문자, 소문자 사이에 다른 문자가 있어서 불필요한 공간 낭비가 발생합니다</p><p></p> <pre class="brush:php;toolbar:false">// by 司徒正美 getIndex(c){ if(c 97 return c - 97 + 26+ 11 } }
그러면 관련 방법은 c-= 48을 c = this.getIndex(c)
Test
var trie = new Trie(); trie.insert("I"); trie.insert("Love"); trie.insert("China"); trie.insert("China"); trie.insert("China"); trie.insert("China"); trie.insert("China"); trie.insert("xiaoliang"); trie.insert("xiaoliang"); trie.insert("man"); trie.insert("handsome"); trie.insert("love"); trie.insert("Chinaha"); trie.insert("her"); trie.insert("know"); var map = {} trie.preTraversal(function(node, str){ if(node.isEnd){ map[str] = node.numEnd } }) for(var i in map){ console.log(i+" 出现了"+ map[i]+" 次") } console.log("包含Chin(包括本身)前缀的单词及出现次数:"); //console.log("China") var map = {} trie.preTraversal(function(node, str){ if(str.indexOf("Chin") === 0 && node.isEnd){ map[str] = node.numEnd } }) for(var i in map){ console.log(i+" 出现了"+ map[i]+" 次") }
Trie 트리와 기타 데이터 구조의 비교
Trie Trees로 변경하는 것입니다. and Binary Search Trees
이진 검색 트리는 우리가 접하게 되는 가장 초기의 트리 구조여야 합니다. 우리는 데이터 크기가 n일 때 이진 검색 트리 삽입, 검색 및 삭제 작업의 시간 복잡도가 일반적이라는 것을 알고 있습니다. 오직 O(log n), 최악의 경우 전체 트리의 모든 노드는 단 하나의 자식 노드만을 가지며, 이는 선형 리스트로 변질됩니다. 이때 삽입, 검색, 삭제 작업의 시간 복잡도는 O(n)입니다. ).
일반적으로 Trie 트리의 높이 n은 검색 문자열의 길이 m보다 훨씬 크기 때문에 검색 연산의 시간 복잡도는 대개 O(m)이고, 최악의 경우 시간 복잡도는 O(n)입니다. ). Trie 트리의 최악의 경우 검색이 이진 검색 트리보다 빠르다는 것을 쉽게 알 수 있습니다.
이 문서의 Trie 트리는 문자열을 예로 사용합니다. 실제로 키의 적합성에 대한 엄격한 요구 사항이 있습니다. 키가 부동 소수점 숫자인 경우 전체 Trie 트리가 매우 길어지고 노드가 늘어날 수 있습니다. 읽기가 매우 어렵습니다. 이 경우 Trie 트리를 사용하여 데이터를 저장하는 것은 적합하지 않습니다. 이 문제는 이진 검색 트리에는 존재하지 않습니다.
트리 트리와 해시 테이블
해시 충돌 문제를 고려해보세요. 우리는 일반적으로 해시 테이블의 복잡도를 O(1)이라고 말합니다. 사실 엄밀히 말하면 이는 완벽에 가까운 해시 테이블의 복잡도입니다. 또한, 해시 함수 자체가 필요로 하는 부분도 고려해야 합니다. 검색 문자열을 순회하는 데 복잡도는 O(m)입니다. 서로 다른 키가 "동일 위치"에 매핑되면(폐쇄 해싱을 고려하면 이 "동일 위치"는 일반 연결 목록으로 대체될 수 있음) 검색의 복잡성은 "동일 위치" 숫자 아래의 노드 수에 따라 달라집니다. 따라서 최악의 경우 해시 테이블은 단방향 연결 목록이 될 수도 있습니다.
Trie 트리는 키의 알파벳 순서에 따라 더 쉽게 정렬할 수 있습니다(전체 트리는 순서대로 한 번 탐색됩니다). 이는 대부분의 해시 테이블(해시 테이블에는 일반적으로 다른 키에 대한 기능이 없습니다) 순서와 다릅니다.
이상적인 상황에서 해시 테이블은 O(1) 속도로 빠르게 목표에 도달할 수 있습니다. 테이블이 매우 커서 디스크에 배치해야 하는 경우 해시 테이블의 검색 액세스는 아래에서 한 번만 수행하면 됩니다. 이상적인 상황입니다. 그러나 Trie 트리에서 액세스하는 디스크 수는 노드 깊이와 동일해야 합니다.
Trie 트리는 해시 테이블보다 더 많은 공간을 필요로 하는 경우가 많습니다. 하나의 노드가 하나의 문자를 저장하는 상황을 고려하면 문자열을 저장할 때 이를 별도의 블록으로 저장할 방법이 없습니다. Trie 트리의 노드 압축은 이 문제를 크게 완화할 수 있으며 이에 대해서는 나중에 설명하겠습니다.
Trie tree의 개선
Bitwise Trie(Bitwise Trie)
원칙적으로 일반 Trie 트리에 저장되는 가장 작은 단위가 문자라는 점을 제외하면 일반 Trie 트리와 유사하지만 Bitwise Trie는 비트만 저장합니다. 비트 데이터에 대한 액세스는 CPU 명령에 의해 한 번 직접 구현됩니다. 바이너리 데이터의 경우 이론적으로 일반 Trie 트리보다 빠릅니다.
노드 압축.
분기 압축: 안정적인 Trie 트리를 위해 기본적으로 검색 및 읽기 작업이 수행되며 일부 분기는 압축될 수 있습니다. 예를 들어 이전 그림에서 가장 오른쪽 가지의 inn은 일반 하위 트리로 존재하지 않고 노드 "inn"으로 직접 압축될 수 있습니다. Radix 트리는 Trie 트리가 너무 깊어지는 문제를 해결하기 위해 이 원리를 기반으로 합니다.
노드 매핑 테이블: 이 방법은 Trie 트리의 노드가 거의 완전히 결정되었을 때에도 사용됩니다. 요소가 숫자인 차원 다차원 배열 배열(예: Triple Array Trie)로 표현되며, 추가 매핑 테이블이 도입되더라도 Trie 트리 자체를 저장하는 공간 오버헤드는 더 작아집니다.
접두사 트리의 적용
접두사 트리는 여전히 이해하기 쉽고 적용 범위도 매우 넓습니다.
(1) 문자열의 빠른 검색
사전 트리의 쿼리 시간 복잡도는 O(logL)이고 L은 문자열의 길이입니다. 따라서 효율성은 여전히 상대적으로 높습니다. 사전 트리는 해시 테이블보다 더 효율적입니다.
(2) 문자열 정렬
위 그림을 보면 단어가 정렬되어 있고, 알파벳 순서가 먼저 순회되는 것을 쉽게 알 수 있습니다. 불필요한 공통 부분 문자열을 줄입니다.
(3) 가장 긴 공통 접두사
inn과 int의 가장 긴 공통 접두사는 in입니다. 사전 트리를 문자 n으로 순회하면 이 단어의 공통 접두사는 이때 in입니다.
(4) 자동으로 접두사 일치 및 접미사 표시
사전이나 검색 엔진을 사용할 때 appl을 입력하면 접두사가 appl인 항목이 자동으로 표시됩니다. 그런 다음 사전 트리를 통해 얻을 수 있습니다. 앞서 언급한 것처럼 사전 트리는 나머지 접미사를 탐색하고 표시하기만 하면 됩니다.
관련 권장사항:
ztrIee의 백엔드 페이지 개발 튜토리얼과 결합된 uery EasyUI 정보
Word PHP는 Trie 트리(사전 트리)를 구현합니다
위 내용은 javascript trie 접두사 트리 코드에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

각각의 엔진의 구현 원리 및 최적화 전략이 다르기 때문에 JavaScript 엔진은 JavaScript 코드를 구문 분석하고 실행할 때 다른 영향을 미칩니다. 1. 어휘 분석 : 소스 코드를 어휘 단위로 변환합니다. 2. 문법 분석 : 추상 구문 트리를 생성합니다. 3. 최적화 및 컴파일 : JIT 컴파일러를 통해 기계 코드를 생성합니다. 4. 실행 : 기계 코드를 실행하십시오. V8 엔진은 즉각적인 컴파일 및 숨겨진 클래스를 통해 최적화하여 Spidermonkey는 유형 추론 시스템을 사용하여 동일한 코드에서 성능이 다른 성능을 제공합니다.

실제 세계에서 JavaScript의 응용 프로그램에는 서버 측 프로그래밍, 모바일 애플리케이션 개발 및 사물 인터넷 제어가 포함됩니다. 1. 서버 측 프로그래밍은 Node.js를 통해 실현되며 동시 요청 처리에 적합합니다. 2. 모바일 애플리케이션 개발은 재교육을 통해 수행되며 크로스 플랫폼 배포를 지원합니다. 3. Johnny-Five 라이브러리를 통한 IoT 장치 제어에 사용되며 하드웨어 상호 작용에 적합합니다.

일상적인 기술 도구를 사용하여 기능적 다중 테넌트 SaaS 응용 프로그램 (Edtech 앱)을 구축했으며 동일한 작업을 수행 할 수 있습니다. 먼저, 다중 테넌트 SaaS 응용 프로그램은 무엇입니까? 멀티 테넌트 SAAS 응용 프로그램은 노래에서 여러 고객에게 서비스를 제공 할 수 있습니다.

이 기사에서는 Contrim에 의해 확보 된 백엔드와의 프론트 엔드 통합을 보여 주며 Next.js를 사용하여 기능적인 Edtech SaaS 응용 프로그램을 구축합니다. Frontend는 UI 가시성을 제어하기 위해 사용자 권한을 가져오고 API가 역할 기반을 준수하도록합니다.

JavaScript는 현대 웹 개발의 핵심 언어이며 다양성과 유연성에 널리 사용됩니다. 1) 프론트 엔드 개발 : DOM 운영 및 최신 프레임 워크 (예 : React, Vue.js, Angular)를 통해 동적 웹 페이지 및 단일 페이지 응용 프로그램을 구축합니다. 2) 서버 측 개발 : Node.js는 비 차단 I/O 모델을 사용하여 높은 동시성 및 실시간 응용 프로그램을 처리합니다. 3) 모바일 및 데스크탑 애플리케이션 개발 : 크로스 플랫폼 개발은 개발 효율을 향상시키기 위해 반응 및 전자를 통해 실현됩니다.

JavaScript의 최신 트렌드에는 Typescript의 Rise, 현대 프레임 워크 및 라이브러리의 인기 및 WebAssembly의 적용이 포함됩니다. 향후 전망은보다 강력한 유형 시스템, 서버 측 JavaScript 개발, 인공 지능 및 기계 학습의 확장, IoT 및 Edge 컴퓨팅의 잠재력을 포함합니다.

JavaScript는 현대 웹 개발의 초석이며 주요 기능에는 이벤트 중심 프로그래밍, 동적 컨텐츠 생성 및 비동기 프로그래밍이 포함됩니다. 1) 이벤트 중심 프로그래밍을 사용하면 사용자 작업에 따라 웹 페이지가 동적으로 변경 될 수 있습니다. 2) 동적 컨텐츠 생성을 사용하면 조건에 따라 페이지 컨텐츠를 조정할 수 있습니다. 3) 비동기 프로그래밍은 사용자 인터페이스가 차단되지 않도록합니다. JavaScript는 웹 상호 작용, 단일 페이지 응용 프로그램 및 서버 측 개발에 널리 사용되며 사용자 경험 및 크로스 플랫폼 개발의 유연성을 크게 향상시킵니다.

Python은 데이터 과학 및 기계 학습에 더 적합한 반면 JavaScript는 프론트 엔드 및 풀 스택 개발에 더 적합합니다. 1. Python은 간결한 구문 및 풍부한 라이브러리 생태계로 유명하며 데이터 분석 및 웹 개발에 적합합니다. 2. JavaScript는 프론트 엔드 개발의 핵심입니다. Node.js는 서버 측 프로그래밍을 지원하며 풀 스택 개발에 적합합니다.


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

Dreamweaver Mac版
시각적 웹 개발 도구

WebStorm Mac 버전
유용한 JavaScript 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

mPDF
mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.
