I'm looking for a good way to do fuzzy matching of a tree against a family of trees.
I know how to look for an exact match between two trees. Just do simultaneous traversals down both of them and see if they're the same.
Now, I would like to (1) quickly match against multiple trees, perhaps on the order of thousands of trees; and (2) do a fuzzy match (for example, severals leaf nodes may be mismatched, but that's ok).
For an exact match against multiple trees, I could hash each tree. But the fuzzy match against multiple trees seems difficult. Any ideas?
You could do it if you think sql-style. Make a lookup table listing each individual leaf node to the subtrees that contain it. Then, to perform a match, look up each leaf underneath the node you want to find matches for, increment a counter for each node that matches at least one of the leaves, and sort by score.
Name:
Anonymous2009-03-04 0:14
Serialize the trees and then use some form of string matching on them. If you really wanted to be an obnoxious OPTIMIZATION faggot, even when the bottle neck in this scenario will be absolutely nowhere near serializing the tree; then you could avoid serializing and just somewhat modify/reimplement other fuzzy algorithms to work on the fly across your tree. If you actually wanted extremely advanced matching; like perhaps a tree and its post-order equivalent to be considered nearly identical then you would probably need to come up with your own algorithm; and be a Ph.D student with extensive experience in the related field.
>>4 like perhaps a tree and its post-order equivalent to be considered nearly identical >>3 would provide that capability with no string crap needed.
Name:
Anonymous2009-03-04 18:32
>>5 increment a counter for each node that matches at least one of the leaves, and sort by score.
Yeah, and this is obviously an extremely complex algorithm that will be able to match very well right? Jesus christ.
That was a very simple example to get >>1 started, and it's certainly more efficient and flexible than serialising and comparing as strings. What is this, Tcl?
more efficient and flexible
Efficient yes, flexible- what the fuck are you smoking? To make that flexible at all you would need to completely rewrite it into much the manner than fuzzy string matching is done. It accounts absolutely NOTHING for ordering or structure. Are you telling me the tree: b
a r
t n o a
is exactly the same as the tree: a
n r
t a b o
or that the following tree is more similar: b
a r
t n e a
And anyway, your other arguments are pretty much invalid too. It is certainly not more effecient to try and write a complex fuzzy matching algorithm from scratch than to use an existing peice of code. In terms of speed... well; I just tested on java and the time taken to serialize a tree is actually less than the time taken to iterate over a tree and store a reference to each node in a lookup table.
Name:
Anonymous2009-03-05 2:33
OP here. Suppose I want to find all similar trees to my target tree. Is there any way to avoid scanning through all the stored trees and comparing them to my target (e.g. >>4 that suggests serialising them and then running a Levenstein distance algorithm between each one and my target tree)?
I would ideally like some way to hash the trees so that the resulting hash value can be compared by distance. For example, if my target tree has a hash value of 42 and I provide a "fuzziness" value of 10, I can search for all trees with values in the range of [32,52]. Would that be be possible?
>>20 Explanation \Ex`pla*na"tion\, n. [L. explanatio: cf. OF.
esplanation.]
1. The act of explaining, expounding, or interpreting; the
act of clearing from obscurity and making intelligible;
as, the explanation of a passage in Scripture, or of a
contract or treaty.
[1913 Webster]
2. That which explains or makes clear; as, a satisfactory
explanation.
[1913 Webster]
3. The meaning attributed to anything by one who explains it;
definition; interpretation; sense.
[1913 Webster]
Different explanations [of the Trinity]. --Bp.
Burnet.
[1913 Webster]
4. A mutual exposition of terms, meaning, or motives, with a
view to adjust a misunderstanding, and reconcile
differences; reconciliation; agreement; as, to come to an
explanation.
>>23 Act \Act\, v. t. [imp. & p. p. Acted; p. pr. & vb. n.
Acting.] [L. actus, p. p. of agere to drive, lead, do; but
influenced by E. act, n.]
1. To move to action; to actuate; to animate. [Obs.]
[1913 Webster]
Self-love, the spring of motion, acts the soul.
--Pope.
[1913 Webster]
2. To perform; to execute; to do. [Archaic]
[1913 Webster]
That we act our temporal affairs with a desire no
greater than our necessity. --Jer. Taylor.
[1913 Webster]
Industry doth beget by producing good habits, and
facility of acting things expedient for us to do.
--Barrow.
[1913 Webster]
Uplifted hands that at convenient times
Could act extortion and the worst of crimes.
--Cowper.
[1913 Webster]
3. To perform, as an actor; to represent dramatically on the
stage.
[1913 Webster]
4. To assume the office or character of; to play; to
personate; as, to act the hero.
[1913 Webster]
5. To feign or counterfeit; to simulate.
[1913 Webster]
With acted fear the villain thus pursued. --Dryden.
[1913 Webster]
To act a part, to sustain the part of one of the characters
in a play; hence, to simulate; to dissemble.
To act the part of, to take the character of; to fulfill
the duties of.
[1913 Webster]
If the trees will mostly match, hash every subtree.
If they mostly won't, just be sure you bail out as soon as you exceed the treshold.
Name:
Anonymous2009-03-05 13:31
Define ``Move''
Name:
Anonymous2009-03-05 13:34
>>26 Move \Move\, v. i.
1. To change place or posture; to stir; to go, in any manner,
from one place or position to another; as, a ship moves
rapidly.
[1913 Webster]
The foundations also of the hills moved and were
shaken, because he was wroth. --Ps. xviii.
7.
[1913 Webster]
On the green bank I sat and listened long, . . .
Nor till her lay was ended could I move. --Dryden.
[1913 Webster]
2. To act; to take action; to stir; to begin to act; as, to
move in a matter.
[1913 Webster]
3. To change residence; to remove, as from one house, town,
or state, to another.
[1913 Webster]
4. (Chess, Checkers, etc.) To change the place of a piece in
accordance with the rules of the game.
[1913 Webster]
A wiki is a page or collection of Web pages designed to enable anyone[citation needed] who accesses it to contribute or modify content, using a simplified[citation needed]markup language.[1][2] Wikis are often[citation needed] used to create collaborative websites[citation needed] and to power community websites. The collaborative encyclopedia Wikipedia is one of the best-known wikis.[2] Wikis are used in business to provide intranet and Knowledge Management systems. Ward Cunningham[citation needed], the developer of the first wiki software, WikiWikiWeb, originally described it as "the simplest online database that could possibly work".[3]
"Wiki" (/wiːkiː/) is a Hawaiian word for "fast".[4] "Wiki Wiki" is a reduplication[citation needed]. "Wiki" can be expanded as "What I Know Is", but this is a backronym.[5]
OP requests more serious discussion than "chaff chaff chaff chaff."
Name:
Anonymous2009-03-07 1:37
┎┰─────────────────────────────────────────────────────────────────────────┐
┃┃ _.-. The neutrality of this post is disputed. │
┃┃ /\|/\ Please see the discussion on the talk page. │
┃┃ --|¯¯ Please do not remove this message until the dispute is resolved. │
┣╋─────────────────────────────────────────────────────────────────────────┤
┃┃ ,_,_ This post does not cite any references or sources. │
┃┃ \ \?\ Please help improve this post by adding citations to reliable │
┃┃ '='=` sources. Unverifiable material may be challenged and removed. │
┖┸─────────────────────────────────────────────────────────────────────────┘
Name:
Anonymous2009-03-07 2:58
┎┰─────────────────────────────────────────────────────────────────────────┐
┃┃ |_ \This thread is in need of "GRUNNUR". Please help recruit │
┃┃ |_)(_) a Fjölnir programmer or improve this thread yourself. │
┃┃ | See the talk page for details. │
┖┸─────────────────────────────────────────────────────────────────────────┘
Name:
Anonymous2009-03-07 4:52
+----------------------------------------------------------------------------+
| `/°< --- Have you read your SICP today? Please help improve world4ch |
| / /, by reading SICP and watching the SICP video lectures. |
|.)_ ) Return when you have reached Satori. |
+----------------------------------------------------------------------------+