트리를 활용한 문자열 비교 알고리즘
해당 알고리즘은 결정적 유한 오토마타를 학습하면서 떠오른 아이디어로 개발하였습니다.
결정적 유한 상태 기계 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. -->
ko.wikipedia.org
기존 map을 활용하여 중복을 제거하고, containsKey로 해당 문자열을 포함하고 있는지 체크하는 방식이 아닌,
트리를 활용하여 중복도 제거하고, 부분 문자열이 아닌 특정 문자열이 있는지 체크하는 알고리즘 입니다.
기존의 트리를 생각한다면 이런방식의 무방향 트리나, 방향이 있는 트리를 생각할 것입니다.
이와 비슷한 형태로 트리를 만들어 봅시다.
트리의 노드에는 번호, 간선에는 문자들이 이루어져 있습니다.
0에서 3에 도달하기까지 abc라는 문자열이 만들어지게 됩니다.
이 트리를 활용할 경우에는 문제가 발생합니다.
ab, abc라는 단어가 사전에 있는 경우, abc만 사전에 있다고 판별짓기 때문입니다.
이를 보완하기 위해서는 오토마타의 마지막 노드의 위치를 나타내는 변수가 필요합니다.
이런식으로 트리를 만들게 될 경우, 마지막 노드가 3인 경우에만 해당 단어가 사전에 있다고 판별할 수 있습니다.
ab인 경우 끝노드가 아니므로 단어가 있지 않다고 판별, abc의 경우 끝 노드 3에 해당하므로 판별 할 수 있습니다.
ab가 사전에 있는 경우, 2번에 끝노드 처리를 할 경우, ab와 abc 모두 사전에 있다고 판별할 수 있습니다.
해당 트리는 여러가지 방식으로 구현할 수 있습니다.
map<map>, set
map<list>, set
map<list>
으로 구현한 알고리즘의 차이점에 대해서 설명드리도록 하겠습니다.
기본적으로 map의 containsKey로 구현한 경우
class map_test {
HashMap<String, Integer> map = new HashMap<>();
ArrayList<String> arr;
public map_test(ArrayList<String> arr) {
this.arr = arr;
}
public void test() {
int count = 0;
for (String s : arr) {
if (!map.containsKey(s)) {
map.put(s, count++);
}
}
long beforeTime = System.currentTimeMillis();
for (String s : arr) {
map.containsKey(s);
}
System.out.println("시간차이(m) : " + (System.currentTimeMillis() - beforeTime));
}
}
사전에 특정 문자열이 포함되어 있는지 구현하라고 할 때, 대부분 작성하는 형식입니다.
map으로 구현하였으나, set의 경우 내부적으로 map<String, Object> 형식으로 활용하기 때문에 차이는 별로 없습니다.
map<map>, set으로 구현한 경우
class graph_test{
Map<Integer, Map<Character, Integer>> transitions = new HashMap<>();
HashSet<Integer> lastStates = new HashSet<>();
ArrayList<String> arr;
public graph_test(ArrayList<String> arr){
this.arr = arr;
}
public void test(){
int count = 0;
for (String s : arr) {
int state = 0;
for(int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if (!transitions.isEmpty() && transitions.containsKey(state)) {
if (transitions.get(state).containsKey(c)) {
state = transitions.get(state).get(c);
} else {
transitions.get(state).put(c, ++count);
state = count;
}
} else {
transitions.put(state, new HashMap<>());
transitions.get(state).put(c, ++count);
state = count;
}
if (j == s.length() - 1) {
lastStates.add(state);
}
}
}
long beforeTime = System.currentTimeMillis();
int state = 0;
for(String s : arr){
for(int j = 0; j < s.length(); j++){
if(transitions.isEmpty() || transitions.get(state) == null|| transitions.get(state).isEmpty()){
break;
}
if(transitions.get(state).containsKey(s.charAt(j))){
state = transitions.get(state).get(s.charAt(j));
}
}
if(lastStates.contains(state)){
}
}
System.out.println("시간차이(m) : "+ (System.currentTimeMillis() - beforeTime));
}
}트리 형태로 구현한 경우 입니다.
lastStates를 통해 마지막 노드의 위치를 중복제거하여 저장합니다.
이후 사전을 통해 문자열을 찾을 때, 해당 노드에 도달한 경우 사전에 있는 단어로 체크하게 됩니다.
map<list>, set으로 구현한 경우
class graph_test {
Map<Integer, List<Node>> transitions = new HashMap<>();
Set<Integer> lastStates = new HashSet<>();
List<String> arr;
public graph_test(ArrayList<String> arr) {
this.arr = arr;
}
public void test() {
int count = 0;
for (String s : arr) {
int state = 0;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if(!transitions.isEmpty() && transitions.containsKey(state)){
boolean flag = false;
for(Node n : transitions.get(state)){
if(n.line == c){
state = n.end;
flag = true;
break;
}
}
if(flag){
continue;
}
}
if (transitions.isEmpty() || !transitions.containsKey(state)) {
transitions.put(state, new ArrayList<>());
}
transitions.get(state).add(new Node(c, ++count));
state = count;
}
lastStates.add(state);
}
long beforeTime = System.currentTimeMillis();
int state = 0;
for (String s : arr) {
for(int j = 0; j < s.length(); j++){
if(transitions.isEmpty() || transitions.get(state) == null|| transitions.get(state).isEmpty()){
break;
}
for(Node n : transitions.get(state)){
if(n.line == s.charAt(j)){
state = n.end;
break;
}
}
}
if (lastStates.contains(state)) {
}
}
System.out.println("시간차이(m) : " + (System.currentTimeMillis() - beforeTime));
}
}
class Node {
char line;
int end;
public Node(char line, int end) {
this.line = line;
this.end = end;
}
}트리의 간선과 도착노드를 map이 아닌 List로 구현한 경우입니다.
2개의 데이터를 한 리스트에 저장해야 하므로 Node라는 class를 활용했습니다.
map<list>로 구현한 경우
class graph_test {
Map<Integer, List<Node>> transitions = new HashMap<>();
List<String> arr;
public graph_test(List<String> arr) {
this.arr = arr;
}
public void test() {
int count = 0;
for (String s : arr) {
int state = 0;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if(!transitions.isEmpty() && transitions.containsKey(state)){
boolean flag = false;
for(Node n : transitions.get(state)){
if(n.line == c){
state = n.end;
flag = true;
break;
}
}
if(flag){
continue;
}
}
if (transitions.isEmpty() || !transitions.containsKey(state)) {
transitions.put(state, new ArrayList<>());
}
transitions.get(state).add(new Node(c, ++count, j == s.length() - 1));
state = count;
}
}
long beforeTime = System.currentTimeMillis();
int state = 0;
for(String s : arr){
for(int j = 0; j < s.length(); j++){
if(transitions.isEmpty() || transitions.get(state) == null|| transitions.get(state).isEmpty()){
break;
}
for(Node n : transitions.get(state)){
if(n.line == s.charAt(j)){
if(!n.endword){
state = n.end;
}
break;
}
}
}
}
System.out.println("시간차이(m) : " + (System.currentTimeMillis() - beforeTime));
}
}
class Node {
char line;
int end;
boolean endword;
public Node(char line, int end, boolean endword) {
this.line = line;
this.end = end;
this.endword = endword;
}
}lastStates라는 끝나는 노드에 대한 정보를 map<list>에 모두 담은 경우입니다.
| map | map<map>, set | map<list>, set | map<list> | |
| 시간 | 235 | 79 | 84 | 440 |
해당 시간은 트리를 만드는 시간(전처리)을 제외한 시간입니다.
트리를 만들 경우, 전체를 다 찾기 전에 탈출하는 경우도 발견되어 확실히 map의 containsKey를 활용한 것보다 시간이 적게 소요되는 것을 볼 수 있습니다.
이후 map<list>의 경우 list에 contains를 사용하다보니 map의 containsKey를 사용할 때 보다 시간이 더 오래 소요되는 것을 볼 수 있습니다.
결론
- contains를 사용하지 않을 경우, list를 사용하여 메모리적으로 이득을 볼 수 있습니다.
- containsKey로 찾는 방식이 아닌, 트리를 활용하여 찾을 경우 더 빠르게 찾을 수 있습니다.
- 오토마타의 재귀 방식을 사용하여 구현하는 방법이 있다면, 트리의 간선과 노드의 수가 줄어들어 메모리적으로 더 이득을 볼 수 있을거 같습니다