| 词条 | Lowest common ancestor |
| 释义 |
In graph theory and computer science, the lowest common ancestor (LCA) of two nodes {{mvar|v}} and {{mvar|w}} in a tree or directed acyclic graph (DAG) {{mvar|T}} is the lowest (i.e. deepest) node that has both {{mvar|v}} and {{mvar|w}} as descendants, where we define each node to be a descendant of itself (so if {{mvar|v}} has a direct connection from {{mvar|w}}, {{mvar|w}} is the lowest common ancestor). The LCA of {{mvar|v}} and {{mvar|w}} in {{mvar|T}} is the shared ancestor of {{mvar|v}} and {{mvar|w}} that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from {{mvar|v}} to {{mvar|w}} can be computed as the distance from the root to {{mvar|v}}, plus the distance from the root to {{mvar|w}}, minus twice the distance from the root to their lowest common ancestor {{harv|Djidjev|Pantziou|Zaroliagis|1991}}. In ontologies, the lowest common ancestor is also known as the least common ancestor. In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from {{mvar|v}} and {{mvar|w}} to the root. In general, the computational time required for this algorithm is {{mvar|O(h)}} where {{mvar|h}} is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity. HistoryThe lowest common ancestor problem was defined by {{harvs|last1=Aho|first1=Alfred|author1-link=Alfred Aho|last2=Hopcroft|first2=John|author2-link=John Hopcroft|last3=Ullman|first3=Jeffrey|author3-link=Jeffrey Ullman|year=1973|txt}}, but {{harvs|first1=Dov|last1=Harel|first2=Robert|last2=Tarjan|author2-link=Robert Tarjan|txt|year=1984}} were the first to develop an optimally efficient lowest common ancestor data structure. Their algorithm processes any tree in linear time, using a heavy path decomposition, so that subsequent lowest common ancestor queries may be answered in constant time per query. However, their data structure is complex and difficult to implement. Tarjan also found a simpler but less efficient algorithm, based on the union-find data structure, for computing lowest common ancestors of an offline batch of pairs of nodes. {{harvs|first1=Baruch|last1=Schieber|first2=Uzi|last2=Vishkin|author2-link=Uzi Vishkin|txt|year=1988}} simplified the data structure of Harel and Tarjan, leading to an implementable structure with the same asymptotic preprocessing and query time bounds. Their simplification is based on the principle that, in two special kinds of trees, lowest common ancestors are easy to determine: if the tree is a path, then the lowest common ancestor can be computed simply from the minimum of the levels of the two queried nodes, while if the tree is a complete binary tree, the nodes may be indexed in such a way that lowest common ancestors reduce to simple binary operations on the indices. The structure of Schieber and Vishkin decomposes any tree into a collection of paths, such that the connections between the paths have the structure of a binary tree, and combines both of these two simpler indexing techniques.{{harvs|first1=Omer|last1=Berkman|first2=Uzi|last2=Vishkin|txt|year=1993}} discovered a completely new way to answer lowest common ancestor queries, again achieving linear preprocessing time with constant query time. Their method involves forming an Euler tour of a graph formed from the input tree by doubling every edge, and using this tour to write a sequence of level numbers of the nodes in the order the tour visits them; a lowest common ancestor query can then be transformed into a query that seeks the minimum value occurring within some subinterval of this sequence of numbers. They then handle this range minimum query problem by combining two techniques, one technique based on precomputing the answers to large intervals that have sizes that are powers of two, and the other based on table lookup for small-interval queries. This method was later presented in a simplified form by {{harvs|first1=Michael|last1=Bender|first2=Martin|last2=Farach-Colton|author2-link=Martin Farach-Colton|txt|year=2000}}. As had been previously observed by {{harvtxt|Gabow|Bentley|Tarjan|1984}}, the range minimum problem can in turn be transformed back into a lowest common ancestor problem using the technique of Cartesian trees.Further simplifications were made by {{harvtxt|Alstrup|Gavoille|Kaplan|Rauhe|2004}} and {{harvtxt|Fischer|Heun|2006}}. A variant of the problem is the dynamic LCA problem in which the data structure should be prepared to handle LCA queries intermixed with operations that change the tree (that is, rearrange the tree by adding and removing edges) This variant can be solved using O(logN) time for all modifications and queries. This is done by maintaining the forest using the dynamic trees data structure with partitioning by size; this then maintains a heavy-light decomposition of each tree, and allows LCA queries to be carried out in logarithmic time in the size of the tree. Without preprocessing you can also improve the naïve online algorithm's computation time to O(log h) by storing the paths through the tree using skew-binary random access lists, while still permitting the tree to be extended in constant time ([https://www.fpcomplete.com/user/edwardk/online-lca Edward Kmett (2012)]). This allows LCA queries to be carried out in logarithmic time in the height of the tree. Extension to directed acyclic graphsWhile originally studied in the context of trees, the notion of lowest common ancestors can be defined for directed acyclic graphs (DAGs), using either of two possible definitions. In both, the edges of the DAG are assumed to point from parents to children.
In a tree, the lowest common ancestor is unique; in a DAG of {{mvar|n}} nodes, each pair of nodes may have as much as {{math|n-2}} LCAs {{harv|Bender|Farach-Colton|Pemmasani|Skiena|2005}}, while the existence of an LCA for a pair of nodes is not even guaranteed in arbitrary connected DAGs. A brute-force algorithm for finding lowest common ancestors is given by {{harvtxt|Aït-Kaci|Boyer|Lincoln|Nasr|1989}}: find all ancestors of {{mvar|x}} and {{mvar|y}}, then return the maximum element of the intersection of the two sets. Better algorithms exist that, analogous to the LCA algorithms on trees, preprocess a graph to enable constant-time LCA queries. The problem of LCA existence can be solved optimally for sparse DAGs by means of an {{math|O({{!}}V{{!}}{{!}}E{{!}})}} algorithm due to {{harvtxt|Kowaluk|Lingas|2005}}. {{harvtxt|Dash|Scholz|Herhut|Christianson|2013}} present a unified framework for pre-processing Directed Acyclic Graphs (DAGs) to compute the least upper bound of two vertices in constant time. Their framework uses adaptive pre-processing where the asymptotic costs depend on the number of non-tree (cross) edges in the DAG. Consequently, it is possible to achieve near-linear pre-processing times for sparse DAGs with constant time LCA look-ups. A library of their work is available for public use at.[1]{{harvtxt|Couto|Francisco|Silva|Mário|2011}} present DiShIn a method that extends the computation of the LCA to all disjunctive ancestors in semantic similarity measures. He defines an ancestor as disjunctive if the difference between the number of distinct paths from the two nodes to that ancestor is different from using any lower common ancestor.ApplicationsThe problem of computing lowest common ancestors of classes in an inheritance hierarchy arises in the implementation of object-oriented programming systems {{harv|Aït-Kaci|Boyer|Lincoln|Nasr|1989}}. The LCA problem also finds applications in models of complex systems found in distributed computing {{harv|Bender|Farach-Colton|Pemmasani|Skiena|2005}}. See also
References1. ^{{Cite web | url=http://www.herts.ac.uk/dag-pre-processing-downloadable-code/source-code | title=Try our source code for free}}
| last1 = Alstrup | first1 = Stephen | last2 = Gavoille | first2 = Cyril | last3 = Kaplan | first3 = Haim | last4 = Rauhe | first4 = Theis | title = Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment | journal = Theory of Computing Systems | doi = 10.1007/s00224-004-1155-5 | volume = 37 | issue = 3 | year = 2004 | pages = 441–456 | url = http://www.math.tau.ac.il/~haimk/papers/lnca-submitted.ps| citeseerx = 10.1.1.76.5973
| last1 = Bender | first1 = Michael A. | last2 = Farach-Colton | first2 = Martin |authorlink2 = Martin Farach-Colton | contribution = The LCA problem revisited | title = Proceedings of the 4th Latin American Symposium on Theoretical Informatics | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | volume = 1776 | date = 2000 | pages = 88–94 | doi = 10.1007/10719839_9 | url = http://www.cs.sunysb.edu/~bender/pub/lca.ps| isbn = 978-3-540-67306-4
| last1 = Berkman | first1 = Omer | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin | title = Recursive Star-Tree Parallel Data Structure | journal = SIAM Journal on Computing | volume = 22 | issue = 2 | pages = 221–242 | year = 1993 | doi = 10.1137/0222017| url = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA227803}}.
| last1 = Djidjev | first1 = Hristo N. | last2 = Pantziou | first2 = Grammati E. | last3 = Zaroliagis | first3 = Christos D. | contribution = Computing shortest paths and distances in planar graphs | doi = 10.1007/3-540-54233-7_145 | pages = 327–338 | publisher = Springer | series = Lecture Notes in Computer Science | title = Automata, Languages and Programming: 18th International Colloquium, Madrid, Spain, July 8–12, 1991, Proceedings | volume = 510 | year = 1991| isbn = 978-3-540-54233-9
| last1 = Fischer | first1 = Johannes | last2 = Heun | first2 = Volker | contribution = Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE | title = Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | volume = 4009 | year = 2006 | pages = 36–48 | doi = 10.1007/11780441_5| isbn = 978-3-540-35455-0 | citeseerx = 10.1.1.64.5439
| last1 = Gabow | first1 = Harold N. | last2 = Bentley | first2 = Jon Louis | author2-link = Jon Bentley (computer scientist) | last3 = Tarjan | first3 = Robert E. | author3-link = Robert Tarjan | contribution = Scaling and related techniques for geometry problems | doi = 10.1145/800057.808675 | location = New York, NY, USA | pages = 135–143 | publisher = ACM | title = STOC '84: Proc. 16th ACM Symposium on Theory of Computing | year = 1984| title-link = Symposium on Theory of Computing | isbn = 978-0897911337
| last1 = Harel | first1 = Dov | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan | title = Fast algorithms for finding nearest common ancestors | journal = SIAM Journal on Computing | volume = 13 | issue = 2 | pages = 338–355 | year = 1984 | doi = 10.1137/0213024}}.
| last1 = Kowaluk | first1 = Miroslaw | last2 = Lingas | first2 = Andrzej | editor1-last = Caires | editor1-first = Luís | editor2-last = Italiano | editor2-first = Giuseppe F. | editor2-link = Giuseppe F. Italiano | editor3-last = Monteiro | editor3-first = Luís | editor4-last = Palamidessi | editor4-first = Catuscia | editor5-last = Yung | editor5-first = Moti | contribution = LCA queries in directed acyclic graphs | doi = 10.1007/11523468_20 | pages = 241–248 | publisher = Springer | series = Lecture Notes in Computer Science | title = Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings | volume = 3580 | year = 2005| isbn = 978-3-540-27580-0 | citeseerx = 10.1.1.460.6923
| last1=Dash|first1=Santanu Kumar | last2=Scholz|first2=Sven-Bodo | last3=Herhut|first3=Stephan | last4=Christianson|first4=Bruce | title=A scalable approach to computing representative lowest common ancestor in directed acyclic graphs | journal=Theoretical Computer Science | date=2013 | volume=513 | pages=25–37 |url=http://www.sciencedirect.com/science/article/pii/S0304397513007226 | doi=10.1016/j.tcs.2013.09.030|hdl=2299/12152
| last1 = Schieber | first1 = Baruch | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin | title = On finding lowest common ancestors: simplification and parallelization | journal = SIAM Journal on Computing | volume = 17 | pages = 1253–1262 | year = 1988 | doi = 10.1137/0217079 | issue = 6}}.
| last1 = Couto | first1 = Francisco | last2 = Silva | first2 = Mário | title = Disjunctive shared information between ontology concepts: application to Gene Ontology | journal = Journal of Biomedical Semantics | volume = 2 | year = 2011 | doi = 10.1186/2041-1480-2-5 | pmid = 21884591 | pmc = 3200982 | issue = 1| pages = 5 External links
2 : Theoretical computer science|Trees (graph theory) |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。