TREE SIMILARITY ESTIMATION BY CALCULATION OF pq-GRAM DISTANCE
Annotation
The paper presents an algorithm for similarity estimation of hierarchical data based on the pq-gram distance calculation. The dependence of the algorithm sensitivity on the selected parameters p andq is analyzed. We show how much the result of the algorithm will change at comparing of two trees that have difference in one random node when one of the nodes of the source tree is deleted, renamed, or an extra node is added. It is demonstrated that such analysis enables to select the parameters p and q in relation with the solving problem. The problem of a tree preliminary evaluation is substantiated - an approximate analysis of the initial level of node differences in the selected pq-grams of the compared trees. The basic terms and definitions relating to the tree-based data structuring algorithms are described. Examples of the algorithm practical application and the details of its implementation on a real problem are shown
Keywords
Постоянный URL
Articles in current issue
- TWO-LENS AFOCAL COMPENSATOR FOR THERMAL DEFOCUS CORRECTION OF CATADIOPTRIC SYSTEM
- ATMOSPHERE PRESSURE EFFECT ON THE FIBER OPTIC GYROSCOPE OUTPUT SIGNAL
- CONTROL OF SCATTERING IN OPTICAL FIBER BY FIBER TWIST
- ALGORITHM FOR MOBILE ROBOT CROSS COUNTRY MOTION
- ALGORITHM FOR RESONANCE CONTROL OF IRON MASS FRACTION IN MAGNETITE ORE
- THEORETICAL ANALYSIS OF DYNAMIC SELECTION OF SWITCHING AUXILIARY OBJECTIVES ON XdivK PROBLEM
- ON RESTORATION OF SMEARED COLOR IMAGES
- IMAGE QUALITY ENHANCEMENT BY PROCESSING OF VIDEO FRAMES WITH DIFFERENT EXPOSURE TIME
- AUTOMATIC SECURITY ANALYSIS OF INFORMATION SYSTEMS INDEPENDENTLY OF FORMAL SPECIFICATIONS
- SECURITY MODEL OF MOBILE MULTI-AGENT ROBOTIC SYSTEMS WITH COLLECTIVE MANAGEMENT
- ANOMALY DETECTION IN WIRELESS SENSOR NETWORKS OF «SMART HOME» SYSTEM
- EFFECTIVENESS OF STEGANALYSIS BASED ON MACHINE LEARNING METHODS
- POST-INCIDENT INTERNAL AUDIT PROCEDURE OF COMPUTER DEVICES
- IMPROVED VISUAL ODOMETRY METHOD FOR SIMULTANEOUS UNMANNED AERIAL VEHICLE NAVIGATION AND EARTH SURFACE MAPPING
- FAST TEST ZONE SEARCH ALGORITHM FOR INTERFRAME ENCODING
- TREE SIMILARITY ESTIMATION BY CALCULATION OF pq-GRAM DISTANCE
- GENERATING DATASETS FOR THE BINARY CLASSIFICATION TASK BASED ON THEIR CHARACTERISTIC DESCRIPTIONS
- PARAMETER INTERVALITY OF REMOTE CONTROL SYSTEMS GENERATED WITH ERROR DETECTION MODE IN COMMUNICATION CHANNEL
- HEAT TRANSFER IN A CAVITY WITH ROTATING DISK IN TURBULENT REGIME
- MATHEMATICAL AND NUMERICAL MODELING OF FREE TURNING SEGMENTS OF SELF-REGULATED STATIC-DYNAMIC GAS BEARING
- NUMERICAL ANALYSIS METHODS OF SOFTWARE TEST EFFICIENCY
- ON THE SIMULATION PARADIGM ANALYSIS
- SMART LASER HEAD
- NEW DESIGN METHOD OF OUTPUT ROBUST CONTROL ALGORITHMS