자료구조와 알고리즘 - 벡터 검색 엔진 최적화 방법: HNSW(Hierarchical Navigable Small World Graphs)

1. 브루트 포스 KNN(K-Nearest Neighbors) 방식 벡터 데이터를 이용한 유사도 검색은 이미지, 텍스트, 추천 시스템 등에서 활용되고 있습니다. 벡터 데이터베이스(Vector DB)는 이러한 유사도 검색을 위한 데이터베이스를 말하며, 주어진 쿼리 벡터와 가장 유사한 데이터 포인트를 찾는 데 사용됩니다.   유사도를 검색할 때 가장 단순한 방법은 모든 데이터를 탐색하는 것입니다. 이러한 방식을 보통 KNN이라고 합니다. KNN 알고리즘은 주어진 쿼리 벡터와 데이터베이스 내의 모든 벡터 간의 거리를 계산하여, 가장 가까운 K개의 이웃을 찾는 방식입니다.   벡터 DB에서 모든 데이터를 탐색하여 거리를 계산하는 방식은 가장 직관적이고 간단한 방법입니다. 이 방식을 흔히 "무차별 탐색(Brute..

• format_list_bulleted 자료구조와 알고리즘
• · 2024. 5. 9.
• textsms

자료구조와 알고리즘 - 문자열검색 알고리즘(KMP)

1. 기본적인 문자열 검색 방법 text = "ababab"pattern = "aba"    텍스트 "ababab"에서 "aba"의 패턴을 찾는 간단한 방법 중 하나는, 패턴을 텍스트의 각 위치에서 시작하여 순차적으로 비교하는 것입니다. 이 과정은 다음과 같이 진행됩니다: 1. 텍스트의 첫 번째 문자에서 시작하여, "aba"와 첫 세 문자 "aba"를 비교합니다. 이 경우, 패턴이 일치합니다. 2. 다음으로, 텍스트의 두 번째 문자로 이동하여, "aba"와 "bab"를 비교합니다. 이 경우, 패턴이 일치하지 않습니다. 3. 이후, 텍스트의 세 번째 문자로 이동하여, "aba"와 "aba"를 다시 비교합니다. 이 경우, 다시 패턴이 일치합니다.4. 마지막으로, 텍스트의 네 번째 문자로 이동하여 "aba"와..

• format_list_bulleted 자료구조와 알고리즘
• · 2024. 4. 20.
• textsms

Database - 데이터베이스 정규화

1. 정규화를 배우기 전의 사전 지식들 1) 키(Key) 데이터베이스에서 키는 각 레코드를 고유하게 식별하거나 테이블 간의 관계를 정의하는 데 중요한 역할을 합니다. 다음은 다양한 키의 종류와 예시입니다. 1.1) 슈퍼키 (Super Key)테이블 내에서 유일성을 보장하는 하나 이상의 속성(컬럼) 집합입니다. 최소성은 보장하지 않습니다.고객 테이블에 있는 {고객 아이디, 고객 이름}, {고객 아이디}, {고객 아이디, 고객 이메일} 모두 슈퍼키가 될 수 있습니다.{고객 아이디, 고객 이름}은 고객을 고유하게 식별할 수 있지만, 고객 아이디만으로도 고유성이 보장되므로 최소성을 갖추지 못한 슈퍼키입니다. 1.2) 후보키 (Candidate Key) 테이블에서 유일성과 최소성을 모두 만족하는 키입니다. 즉, ..

• format_list_bulleted 기타
• · 2024. 4. 18.
• textsms

Python - 파이썬 메모리 관리

게시하는 내용은 Cpython(C로 만든 python) 기준입니다.1. 객체와 참조. 객체란 일반적으로 데이터와 해당 데이터에 대한 동작(행위 또는 메서드)를 나타내는 구조를 말합니다. 컴퓨터 용어를 빌리면 객체는 속성(필드)과 메소드를 포함하는 구조입니다. 파이썬 코드를 이루는 거의 모든 것들, 예를 들어 함수,빌트인 타입(정수형,문자열...), 자료구조 등은 모두 객체입니다. 객체가 변수에 할당 되면 참조가 생깁니다.import sysclass Some: def some(self): pass a = Some()print(f"클래스Some의 참조 수: {sys.getrefcount(Some)}개")print(f"변수a의 참조 수: {sys.getrefcount(a)}개")  a는..

• format_list_bulleted 파이썬
• · 2024. 3. 11.
• textsms

자료구조와 알고리즘 - Trie (Prefix Tree)

1.  Trie 개념 Trie(트라이)는 트리 자료 구조의 일종으로, 문자열 검색과 관련된 작업에 사용됩니다. Trie는 각 노드가 하나의 문자를 나타내며, 루트 노드에서부터 각 문자의 연속으로 경로를 형성합니다. 이로써 단어 검색, 접두어 검색, 삽입 등의 작업을 빠르게 수행할 수 있습니다. 이를 응용하여 자동완성, 스펠링 체크 등에 쓰입니다. - Trie의 주요 특징:계층적인 구조: 각 노드가 문자를 나타내며, 노드 간의 관계가 문자열의 구조를 반영한다.공통 접두어 공유: 비슷한 문자열은 동일한 접두어를 공유한다.빠른 검색: 문자열 검색이 효율적이다. 시간 복잡도는 O(L)이며, L은 찾고자 하는 문자열의 길이이다.   2. Trie 구현 방법Trie는 문자열을 각 노드에 저장합니다. 예를 들어 ["..

• format_list_bulleted 자료구조와 알고리즘
• · 2024. 2. 13.
• textsms

자료구조와 알고리즘 - 슬라이딩 윈도우(Sliding Window)

1. 슬라이딩 윈도우 개념  슬라이딩 윈도우(슬라이딩 창)는 원래 데이터 처리와 통신에서 사용되는 기법으로 언급된다. 고정된 크기의 윈도우(창)를 사용하여 데이터를 처리하는 방식을 나타낸다. 이 기법은 주로 통신 프로토콜에서 오류 제어, 흐름 제어, 데이터 전송 등에 활용된다.  코딩테스트와 알고리즘에서는 슬라이딩 윈도우가 배열 또는 리스트에서 고정된 크기의 부분 배열을 효율적으로 처리하는 데 활용되는 개념으로도 사용된다. 특히 연속적인 부분 배열의 합이나 패턴을 찾는 등의 문제에서 슬라이딩 윈도우를 적용하여 코드를 최적화하는 경우가 있다.     2. 예시 문제https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호평소에 문자열을 가지고 노는 것을 좋아하는 민호..

• format_list_bulleted 자료구조와 알고리즘
• · 2024. 1. 2.
• textsms