Introduction to Pattern Matching

https://rosalind.info/problems/trie/

ROSALIND | Introduction to Pattern Matching

Problem

Figure 1. The trie corresponding to the strings 'apple', 'apropos', 'banana', 'bandana', and 'orange'. Each path from root to leaf encodes one of these strings.

Given a collection of strings, their trie (often pronounced "try" to avoid ambiguity with the general term tree) is a rooted tree formed as follows. For every unique first symbol in the strings, an edge is formed connecting the root to a new vertex. This symbol is then used to label the edge.

We may then iterate the process by moving down one level as follows. Say that an edge connecting the root to a node vv is labeled with 'A'; then we delete the first symbol from every string in the collection beginning with 'A' and then treat vv as our root. We apply this process to all nodes that are adjacent to the root, and then we move down another level and continue. See Figure 1 for an example of a trie.

As a result of this method of construction, the symbols along the edges of any path in the trie from the root to a leaf will spell out a unique string from the collection, as long as no string is a prefix of another in the collection (this would cause the first string to be encoded as a path terminating at an internal node).

Given: A list of at most 100 DNA strings of length at most 100 bp, none of which is a prefix of another.

Return: The adjacency list corresponding to the trie TT for these patterns, in the following format. If TT has nn nodes, first label the root with 1 and then label the remaining nodes with the integers 2 through nn in any order you like. Each edge of the adjacency list of TT will be encoded by a triple containing the integer representing the edge's parent node, followed by the integer representing the edge's child node, and finally the symbol labeling the edge.

Sample Dataset

ATAGA
ATC
GAT

Sample Output

1 2 A
2 3 T
3 4 A
4 5 G
5 6 A
3 7 C
1 8 G
8 9 A
9 10 T

 

 이 문제는 패턴 매칭을 위해 trie(트라이라 읽는다)를 구해서 그 안의 edge들과 이어주는 node를 출력하는 문제이다. trie는문자열이 공통된 부분을 따라가면서 갈라지는 뭐 그런 트리이다. 이 문제는 문자열들을 동시에 하나의 인덱스로 진행해서 한번에 trie를 만들어야 한다고 생각하면 복잡하다. 그렇기에 일종의 첫번째 문자열을 기준으로 하나의 트리를 만들고 그 트리를 타가면서 맞지 않은 부분에서 갈라져서 시작하는 그런 감각으로 코드를 만들면 의외로 쉽게 풀린다. 자세한 설명은 코드와 함께 설명하겠다.

def building_trie(patterns):
    trie={1:{}}#trie를 저장
    edges=[]#엣지들과 이어진 노드들 저장
    node_id=1#새로운 노드 나타날시 노드id매겨주기

    for pattern in patterns:#여러 문자열들 중 하나의 문자열
        current_node = 1#일단 처음부터 시작
        for char in pattern:#하나의 문자열에서 하나의 알파벳
            if char in trie[current_node]:#지금 있는 노드에서 이 알파벳으로 이어진 노드가 있다면
                current_node = trie[current_node][char]#지금 노드는 이어진 노드로 이동
            else:#만약 없다면
                node_id+=1#새로운 노드id 매기기
                trie[current_node][char] = node_id#지금 노드와 새로운 노드 이어주기
                edges.append((current_node,node_id,char))#지금노드,새로운노드,엣지 저장
                current_node = node_id#지금 노드는 새로운 노드로

                trie[node_id]={}#새로운 노드에서 이어지는 딕셔너리 만들기

    return edges

#파일 열어 문자열들 저장
if __name__ == '__main__':
    with open(r'파일경로','r') as f:
        patterns=[]
        for i in f.readlines():
            patterns.append(i.rstrip())

ans = building_trie(patterns)

#결과값을 그대로 파일에 저장
with open(r'파일경로','w',encoding='utf-8') as f:
    for edge in ans:
        print(f'{edge[0]} {edge[1]} {edge[2]}',file=f)

 

tire 딕셔너리가 조금 비직관적인데 설명을 더 하자면 trie딕셔너리는 일단 부모 노드를 key로 가진다. 그 이후 value는 부모 노드에서 이어지는 엣지와 자식노드를 나타내는데 이 value또한 dictionary이다. valeu인 딕셔너리는 엣지를 key로 하고 자식 노드를 value로 한다. 결론적으로 딕셔너리를 이중으로 써서 부모노드와 엣지와 자식노드 3개를 동시에 이어지게 표현할 수 있다. 예시로 주어진 케이스로 trie 딕셔너리를 구하면

{1: {'A': 2, 'G': 8}, 2: {'T': 3}, 3: {'A': 4, 'C': 7}, 4: {'G': 5}, 5: {'A': 6}, 6: {}, 7: {}, 8: {'A': 9}, 9: {'T': 10}, 10: {}} 처럼 나온다. 

 이 문제는 처음에 하나의 문자열로 아에 새로운 트라이를 만들고 여기에 붙여나간다는 발상이 어렵다고 개인적으로 생각한다.