Earticle

Detecting similarity or plagiarism in the academic research publications, source code, etc. has been a long time complex and time consuming task. Several algorithms, tools and websites exist that try to find plagiarism or possible plagiarism in those human creative products. In this paper we used source code plagiarism detection tools to assess the level of plagiarism in source codes. We also investigated issues related to accuracy and challenges in detecting possible plagiarism in students’ assignments. In a second study, we evaluated some tools against detecting possible plagiarism in research papers. Results showed that such process or decision is not binary to make and that subjectivity is high. In addition, there is a need to tune plagiarism detection tools to give criticality or weights by users of those tools to categorize and classify different levels of seriousness for committing plagiarism.

Studying patterns in DNA sequences has been for years the subject of many research papers in bioinformatics. This paper evaluates two algorithms used for DNA comparison. Those are: Longest Common Substring and Subsequence (LCS, LCSS). Evaluation is performed based on the different code implementations for those two algorithms. Accuracy and performance are the two major criteria that are used for the evaluation of algorithms’ implementation. Results showed that while those two algorithms are popular, their implementations are not consistent through research papers or websites that use and implement those algorithms for DNA sequence comparison.

본 논문에서는 새로운 외부 메모리 인덱스 자료 구조인 접미사 B-tree를 제안한다. 접미사 B-tree는 String B-tree와 마찬가지로 문자열을 키로 가지는 B-tree이다. String B-tree의 노드는 복잡한 Patricia ie로 구현된 반면, 접미사 B-tree의 노드는 일반적인 B-tree처럼 배열로 구현되어 보다 간단하고 구현하기 쉽다. 그럼에도 불구하고 접미사 B-tree에서 배열을 이용하여 String B-tree만큼 효율적으로 분기를 찾을 수 있다. 결과적으로 문자열 알고리즘 분야에서 기본적이고 중요한 문제인 문자열 매칭을 String B-tree와 동일한 디스크 접근을 사용하여 수행할 수 있다.

We propose a new external-memory index data structure, the Suffix B-tree. The Suffix B-tree is a B-tree in which the key is a string like the String B-tree. While the node in the String B-tree is implemented with a Patricia trio, the node in the Suffix B-tree is implemented with an array. So the Suffix B-tree is simpler and easier to be Implemented than the String B-tree. Nevertheless, the branching algorithm of the Suffix B-tree is as efficient as that of the String B-tree. Consequently, the Suffix B-tree takes the same worst-case disk accesses as the String B-tree to solve the string matching problem, which is fundamental and important in the area of string algorithms.

유사 문자열 검색을 위해 기존의 기법들은 우선 후보 문자열 집합을 생성한 후에 후보 문자열을 검증하는 방법을 사용한다. 이때, 유사 문자열 검색의 성능을 결정짓는 가장 중요한 요소는 후보 생성 방법이다. 기존의 기법들은 질의 문자열로부터 고정길이 q-그램들을 선택하고, 선택된 q-그램에 해당하는 역리스트를 이용해 후보 문자열을 생성한다. 본 논문에서는 질의 문자열 내의 가변길이 그램들을 사용하여 후보 문자열을 생성할 수 있는 기법과 질의 문자열로부터 최적의 가변길이 그램들의 조합을 선택하는 동적 프로그래밍 알고리즘을 제안한다. 실험을 통해 제안하는 기법이 기존의 기법들 보다 유사 문자열 검색의 성능을 향상시킴을 보인다.

Existing techniques for string similarity search first generate a set of candidate strings and then verify the candidates. The efficiency of string similarity search is highly dependent on candidate generation methods. State of the art techniques select fixed length q-grams from a query string and generate candidates using inverted lists of the selected q-grams. In this paper, we propose a technique to generate candidates using variable length grams of a query string and develop a dynamic programming algorithm that selects an optimal combination of variable length grams from a query string. Experimental results show that the proposed technique improves the performance of string similarity search compared with the existing techniques.