Merging String Sequences by Longest Common Prefixes

スポンサーリンク

概要

• 論文の詳細を見る

• We present LCP Merge, a novel merging algorithm for merging two ordered sequences of strings. LCP Merge substitutes string comparisons with integer comparisons whenever possible to reduce the number of character-wise comparisons as well as the number of key accesses by utilizing the longest common prefixes (LCP) between the strings. As one of the applications of LCP Merge, we built a string merge sort based on recursive merge sort by replacing the merging algorithm with LCP Merge and we call it LCP Merge sort. In case of sorting strings, the computational complexity of recursive merge sort tends to be greater than O(n lg n) because string comparisons are generally not constant time and depend on the properties of the strings. However, LCP Merge sort improves recursive merge sort to the extent that its computational complexity remains O(n lg n) on average. We performed a number of experiments to compare LCP Merge sort with other string sorting algorithms to evaluate its practical performance and the experimental results showed that LCP Merge sort is efficient even in the real-world.

• 一般社団法人 情報処理学会の論文

著者

• Ng Waihong

  Graduate School Of Fundamental Science And Engineering Waseda University

• KAKEHI KATSUHIKO

  Faculty of Science and Engineering, Waseda University

• Kakehi Katsuhiko

  Faculty Of Science And Engineering Waseda University

関連論文

• Cache Efficient Radix Sort for String Sorting(Algorithms and Data Structures)
• Merging String Sequences by Longest Common Prefixes(Algorithm Theory)
• Merging String Sequences by Longest Common Prefixes

スポンサーリンク