TWpower Reading time ~7 minutes

Implement trie and solve basic problem in C++.


Environment and Prerequisite

  • C++


What is Trie?

About Trie

  • Trie : Trie is a tree shape data structure for efficiently searching and storing strings.
  • From root to leaf nodes are strings which stored in trie data structure. We can distinguish end of string by adding terminal variable to each node.
  • By searching DFS method in above picture, we can find that to, tea, ted, ten, A, i, in, inn strings are stored in data structure.


Example of Trie

  • Orange color nodes are inserted strings.
  • be, bee, can, cat, cd are stored in trie.


Purpose of Trie

Purpose

  • The reason why we use trie is in time complexity of string searching. It is much more efficient than linear searching. However there is advantage that searching is efficient but also drawbacks that it saves all children pointer in each node so trie takes many spaces.
  • It can be used in searching keyword autocomplete, searching in dictionary and spelling checking. Reference is in References

Time Complexity

  • Consider L as longest string and M as total number of strings.
  • Creation time complexity : O(M*L), There are total M strings and each string only takes at most L time so it takes O(M*L). Insertion itself takes O(L).
  • Searching time complexity : O(L), It takes at most O(L) of time. Because it is tree structure.


Trie Implementation

  • Codes are base on book Algorithm Problem Solving Strategy


Common

  • Only consider capital alphabets
#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}


Trie Code

  • is_terminal : It represents end of string.
  • void insert(const char * key) : Add new string to trie structure.
  • Trie* find(const char * key) : Check if trie has key(passed string argument) as prefix. If it has key as prefix then return end of key prefix node.
  • bool string_exist(const char * key) : Check if trie has key(passed string argument). If it has key then return true. If not then return false.
struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie() : is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};


Main Function

  • Add check code in main function.
  • Main function checks whether trie works well.
int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert : %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s : be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s : c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


All codes

#include <cstdio>
#include <cstring>

#define ALPHABETS 26

// Convert char to array index
// All are base on capital
int char_to_index(char c){
	return c - 'A';
}

struct Trie{

	bool is_terminal; // this represents end of string
	Trie * children[ALPHABETS];

	// Constructor
	Trie() : is_terminal(false){
		memset(children, 0, sizeof(children));
	}

	// Delete all children
	~Trie(){
		for(int i = 0; i < ALPHABETS; ++i){
			if(children[i])
				delete children[i];
		}
	}

	void insert(const char * key){
		if(*key == '\0'){
			is_terminal = true;
		}
		else{
			int index = char_to_index(*key);

			if(children[index] == 0)
				children[index] = new Trie();
			children[index]->insert(key + 1);
		}
	}

	Trie* find(const char * key){
		if(*key == 0){
			return this;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return NULL;
		}

		return children[index]->find(key+1);
	}

	bool string_exist(const char * key){
		if(*key == 0 && is_terminal){
			return true;
		}

		int index = char_to_index(*key);
		if(children[index] == 0){
			return false;
		}
		return children[index]->string_exist(key + 1);
	}

};

int main (){

	Trie * root = new Trie();

	const char * words[5] = {"be", "bee", "can", "cat", "cd"};

	for(int i = 0; i < 5; ++i){
		printf("insert : %s\n", words[i]);
		root->insert(words[i]);
	}

	printf("\n");

	printf("%s : be\n", root->find("be") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : can\n", root->find("can") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : a\n", root->find("a") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : cat\n", root->find("cat") != 0 ? "Prefix Exist" : "Prefix Not Exist");
	printf("%s : c\n", root->find("c") != 0 ? "Prefix Exist" : "Prefix Not Exist");

	printf("\n");

	printf("%s : c\n", root->string_exist("c") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : be\n", root->string_exist("be") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : bee\n", root->string_exist("bee") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : candy\n", root->string_exist("candy") != 0 ? "String Exist" : "String Not Exist");
	printf("%s : cd\n", root->string_exist("cd") != 0 ? "String Exist" : "String Not Exist");

	delete root;

	return 0;
}


Trie Basic Problem

Baekjoon Online Judge 5052

  • Check if phone number list is in consistency. Print YES if it is in consistency if not then print NO.
  • In consistency means that any number is not prefix to other numbers.
  • Link : https://www.acmicpc.net/problem/5052


Solution and Method

  • It is string processing problem and also it contains prefix processing so using trie data structure is solution.
  • Solution 1 : Insert all phone numbers to trie and search all phone numbers. If there is terminal node(is_terminal value is true) before end of the phone number, then return false.
  • Solution 2 : Check inserted phone number is prefix to other numbers when insert into trie.


Solution Codes

Solution 1

  • Insert all phone numbers to trie and search all phone numbers. If there is terminal node(is_terminal value is true) before end of the phone number, then return false.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];
	Trie() : is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	void insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
		}
		else {
			int index = char_to_index(*key);
			if (next[index] == 0)
				next[index] = new Trie();
			next[index]->insert(key + 1);
		}
	}

	bool find(const char * key) {

		if (*key == '\0') return true;

        // Return false if there is already terminal node before string is the end.
		if (is_terminal) return false;

		int index = char_to_index(*key);
		return next[index]->find(key + 1);
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();
		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);
			root->insert(phone_books[i]);
		}

		bool is_valid = true;
		for (int i = 0; i < n; ++i) {

			if (root->find(phone_books[i]) == false) {
				is_valid = false;
				break;
			}
		}
        delete root;
		printf("%s\n", is_valid ? "YES" : "NO");
	}
	return 0;
}

Solution 2

  • Check inserted phone number is prefix to other numbers when insert into trie.
#include <cstdio>
#include <cstring>

int char_to_index(char c){
	return c - '0';
}

struct Trie {

	bool is_terminal;
	Trie * next[10];

	Trie() : is_terminal(false) {
		memset(next, 0, sizeof(next));
	}

	~Trie() {
		for (int i = 0; i < 10; ++i) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	bool insert(const char * key) {

		if (*key == '\0') {
			is_terminal = true;
			return true;
		}
		else {
			// If it is already terminal node then there is a prefix match
			if(is_terminal == true) return false;

			int index = char_to_index(*key);

			if (next[index] == 0)
				next[index] = new Trie();

			// If next node is already exists and current's next is end of string then there is a prefix match
			else if(next[index] != 0 && *(key + 1) == '\0'){
				return false;
			}
			return next[index]->insert(key + 1);
		}
	}
};

int main() {

	int t;
	char phone_books[10000][11];
	scanf("%d", &t);

	while (t--) {
		int n;
		scanf("%d", &n);

		Trie * root = new Trie();

		bool ret = true;

		for (int i = 0; i < n; ++i) {
			scanf("%s", &phone_books[i]);

			if (ret == false) continue;

			ret = root->insert(phone_books[i]);

		}

		delete root;
		printf("%s\n", ret ? "YES" : "NO");
	}
	return 0;
}


References

TWpower Reading time ~1 minute

도커(Docker) 이미지 이름과 태그 목록을 awk과 tail 명령어를 이용해 가져오는 방법을 알아보자


환경

  • Linux 기반 시스템
  • Bash shell(/bin/bash)
  • Docker
  • awk, tail 명령어


도커(Docker) 이미지 이름 및 태그 가져오기

(기본) 도커 이미지 관련한 목록들 가져오기

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               latest              f68d6e55e065        2 weeks ago         109MB
nginx               stable              ac44715da54a        5 weeks ago         109MB
ubuntu              latest              7698f282e524        2 months ago        69.9MB
centos              centos7.5.1804      cf49811e3cdb        4 months ago        200MB
centos              latest              9f38484d220f        4 months ago        202MB
hello-world         latest              fce289e99eb9        6 months ago        1.84kB


도커 이미지들 ID 가져오기

  • -qa 옵션을 이용해 ID들 가져오기
  • -qa : 모든 이미지들을 보여주며 다른 정보들은 표시하지 않고 ID만 표시합니다.
$ sudo docker images -qa
f68d6e55e065
ac44715da54a
7698f282e524
cf49811e3cdb
9f38484d220f
fce289e99eb9


도커 이미지들 이름 가져오기

  • tail -n +2을 이용해 첫줄을 제외하고 두번째줄부터 목록들을 가져오기 위해 사용하며 첫줄은 각 열에 관한 설명이기 때문에 제외합니다.
  • awk를 이용해 첫번째 열에 대한 부분들만 가져옵니다.
  • $1는 첫번째 열을 의미합니다.
$ sudo docker images | tail -n +2 | awk '{print $1}'
nginx
nginx
ubuntu
centos
centos
hello-world


도커 이미지들 태그 가져오기

  • 위의 방법과 동일한 방법으로 awk명령어에서 변수만 $1에서 $2로 변경
  • $2는 두번째 열을 의미합니다.
$ sudo docker images | tail -n +2 | awk '{print $2}'
latest
stable
latest
centos7.5.1804
latest
latest


도커 이미지들을 태그와 함께 가져오기

  • 위의 방법과 동일한 방법으로 awk명령어에서 변수와 식을 조금 추가
$ sudo docker images | tail -n +2 | awk '{print $1":"$2}'
nginx:latest
nginx:stable
ubuntu:latest
centos:centos7.5.1804
centos:latest
hello-world:latest


참고자료

TWpower Reading time ~1 minute

Pring docker images name and tag list with using awk and tail command.


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)
  • Docker
  • awk, tail command


Get docker images name and tag list

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               latest              f68d6e55e065        2 weeks ago         109MB
nginx               stable              ac44715da54a        5 weeks ago         109MB
ubuntu              latest              7698f282e524        2 months ago        69.9MB
centos              centos7.5.1804      cf49811e3cdb        4 months ago        200MB
centos              latest              9f38484d220f        4 months ago        202MB
hello-world         latest              fce289e99eb9        6 months ago        1.84kB


Get docker images ID

  • Use -qa option to get IDs
  • -qa : Show all docker images and only show images ID
$ sudo docker images -qa
f68d6e55e065
ac44715da54a
7698f282e524
cf49811e3cdb
9f38484d220f
fce289e99eb9


Get docker images name

  • Use tail -n +2 command to exclude first line(first line is header of each column) and to print from second line.
  • Use awk to get first column.
  • $1 means first column
$ sudo docker images | tail -n +2 | awk '{print $1}'
nginx
nginx
ubuntu
centos
centos
hello-world


Get docker images tag

  • Use same awk command like above except modify variable from $1 to $2
  • $2 means second column
$ sudo docker images | tail -n +2 | awk '{print $2}'
latest
stable
latest
centos7.5.1804
latest
latest


Get docker images name with tag

  • Use same awk command like above except modify variable and expression
$ sudo docker images | tail -n +2 | awk '{print $1":"$2}'
nginx:latest
nginx:stable
ubuntu:latest
centos:centos7.5.1804
centos:latest
hello-world:latest


Reference

TWpower Reading time ~1 minute

도커(Docker) 이미지를 파일로 저장하고 불러오자


환경

  • Linux 기반 시스템
  • Bash shell(/bin/bash)
  • Docker


도커(Docker) 이미지를 파일로 저장하기

docker save

기본 형태

docker save [OPTIONS] IMAGE(with tag) [IMAGE...]

옵션

  • --output , -o : 파일명을 명시합니다.

예시

  • docker images list
$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               stable              ac44715da54a        3 weeks ago         109MB
centos              centos7.5.1804      cf49811e3cdb        3 months ago        200MB
  • centos image example by using redirection
$ sudo docker save centos:centos7.5.1804 > centos-centos7.5.1804-image.tar

$ ls -al centos-centos7.5.1804-image.tar
-rw-rw-r-- 1 twpower twpower 207841280 Jul  4 22:55 centos-centos7.5.1804-image.tar
  • nginx image example by using -o option
$ sudo docker save nginx:stable -o nginx-stable-image.tar

$ ls -al nginx-stable-image.tar
-rw------- 1 root root 113060352 Jul  4 22:56 nginx-stable-image.tar


파일을 도커(Docker) 이미지로 불러오기

docker load

기본 형태

docker load [OPTIONS]

옵션

  • --input , -i : 불러올 파일명을 명시합니다.

예시

  • centos image example by using redirection
$ ls -al centos-centos7.5.1804-image.tar
-rw-rw-r-- 1 twpower twpower 207841280 Jul  4 22:55 centos-centos7.5.1804-image.tar

$ sudo docker load < centos-centos7.5.1804-image.tar
4826cdadf1ef: Loading layer  207.8MB/207.8MB
Loaded image: centos:centos7.5.1804

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
centos              centos7.5.1804      cf49811e3cdb        3 months ago        200MB
  • nginx image example by using -i option
$ ls -al nginx-stable-image.tar
-rw------- 1 root root 113060352 Jul  4 22:56 nginx-stable-image.tar

$ sudo docker load -i nginx-stable-image.tar
da9fed87e1d3: Loading layer  54.59MB/54.59MB
0d1174230cc6: Loading layer  3.584kB/3.584kB
Loaded image: nginx:stable

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               stable              ac44715da54a        3 weeks ago         109MB
centos              centos7.5.1804      cf49811e3cdb        3 months ago        200MB


참고자료

TWpower Reading time ~1 minute

Save and Load docker image files.


Environment and Prerequisite

  • Linux base system
  • Bash shell(/bin/bash)
  • Docker


Save docker image to file

docker save

Basic Form

docker save [OPTIONS] IMAGE(by tag) [IMAGE...]

Options

  • --output , -o : Specify output file name.

Examples

  • docker images list
$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               stable              ac44715da54a        3 weeks ago         109MB
centos              centos7.5.1804      cf49811e3cdb        3 months ago        200MB
  • centos image example by using redirection
$ sudo docker save centos:centos7.5.1804 > centos-centos7.5.1804-image.tar

$ ls -al centos-centos7.5.1804-image.tar
-rw-rw-r-- 1 twpower twpower 207841280 Jul  4 22:55 centos-centos7.5.1804-image.tar
  • nginx image example by using -o option
$ sudo docker save nginx:stable -o nginx-stable-image.tar

$ ls -al nginx-stable-image.tar
-rw------- 1 root root 113060352 Jul  4 22:56 nginx-stable-image.tar


Load docker image from file

docker load

Basic Form

docker load [OPTIONS]

Options

  • --input , -i : Specify image file name that will be loaded.

Examples

  • centos image example by using redirection
$ ls -al centos-centos7.5.1804-image.tar
-rw-rw-r-- 1 twpower twpower 207841280 Jul  4 22:55 centos-centos7.5.1804-image.tar

$ sudo docker load < centos-centos7.5.1804-image.tar
4826cdadf1ef: Loading layer  207.8MB/207.8MB
Loaded image: centos:centos7.5.1804

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
centos              centos7.5.1804      cf49811e3cdb        3 months ago        200MB
  • nginx image example by using -i option
$ ls -al nginx-stable-image.tar
-rw------- 1 root root 113060352 Jul  4 22:56 nginx-stable-image.tar

$ sudo docker load -i nginx-stable-image.tar
da9fed87e1d3: Loading layer  54.59MB/54.59MB
0d1174230cc6: Loading layer  3.584kB/3.584kB
Loaded image: nginx:stable

$ sudo docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
nginx               stable              ac44715da54a        3 weeks ago         109MB
centos              centos7.5.1804      cf49811e3cdb        3 months ago        200MB


Reference