Similarity Measure among Structures of Local Government Statute Books based on Tree Edit Distance

Yoichi Takenaka, Takeshi Wakao


A similarity measure between statute books of local governments that can help reveal suggestive similarities is proposed. The regulations of a local government are stored in a statute book, and they are categorized in a layered structure. The layered structure can be described as an ordered tree in computer science, and we define the similarity of statute books as the tree edit distance between two trees. We have calculated the similarities among statute books of the 47 Japanese prefectures and plotted them on a plane using multi-dimensional scaling. The results visually indicate the relationships of similarities among them, and there are several outlier prefectures and clusters. This will help find local governments with similar regulations, which will facilitate the writing or revision of statutes, especially in small local governments, which are typically short staffed.


statute book, local government, similarity measure, tree edit distance


Erik D. Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann(2009), An Optimal Decomposition Algorithm for Tree Edit Distance, ACM Trans. Algorithms, 6(1):2:1-2:19.

Takashi, Harada, Jyunichi Aoki, and Yurika Mashima (2009), Automatic classi- fication of Local Government Statutes based on Clustering methods, In the proceeding of the 9th Study Meeting, The Information Network Law Association, pp. 65–68.

Tokuyasu Kakuta (2010), A Method for Supporting Legislation with Focusing on Analogy to Software Engineering (3), Journal of Law and Politics, vol. 237, chap. 2, pp. 191–252, School of Law, Nagoya University.

Tokuyasu Kakuta (2012), An analysis of regulations of local governments using a supercomputer and the application to a regulation database, Journal of Law and Politics, vol. 246, pp. 69-91, School of Law, Nagoya University.

Tai, Kuo-Chung (1979) The Tree-to-Tree Correction Problem, J. ACM, Vol. 26(3),pp. 422–433.

Yoichi Takenaka and Takeshi Wakao, Automatic Generation of Article Corre- spondence Tables for the Comparison of Local Government Statutes, Natural Language Processing, vol. 19(3), pp. 193–212.

Yoichi Takenaka and Takeshi Wakao, Automatic Extraction of Common Local Government Laws among Prefectures and its Applications, Transaction on Mathematical Modeling and its Application, vol. 8(1), pp. 80–86.

Kaizhong Zhang, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, vol. 18(6),pp. 1245–1262.

Kaizhong Zhang, Rick Statman, and Dennis Shasha, On the Editing Distance Between Unordered Labeled Trees, Information Processing Letters, vol 42(3), pp. 133–139.

Full Text: PDF


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.