Re: need an algo for string sorting
From: Paul E. Black (p.black_at_acm.org)
Date: 08/19/04
- Next message: Randy: "Re: hard disk faster than main memory?"
- Previous message: Thad Smith: "Re: need an algo for string sorting"
- In reply to: Raghavendra Mahuli: "need an algo for string sorting"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 19 Aug 2004 12:08:15 -0400 To: paul.black@nist.gov
On Thu, 19 Aug 2004 10:59:32 +0530, Raghavendra Mahuli wrote:
> I have many strings. I have to sort them. ...
>
> But the complex part is "equivalent-values". it can be defined that "ai" and
> "ae" are equivalent-values. Then, while sorting two strings, i have to
> consider that "ai" and "ae" are equal......only if they come at same
> position in both the strings....
> str1 - dfahaesdhfkj
> str2 - dfahaisds
> ... ae [and ai] appears at position 4 and 5
>
> str3 - haehasdg
> str4 - hhsdaiskdn
> ... [ae and ai appear at different positions] ...
You might be able to replace all occurrences with equivalence class
markers, for instance:
dfahQ7sdhfkj
dfahQ7sds
hQ7hasdg
hhsdQ7skdn
where Q is some character that never appears. It is a prefix or
escape character.
If it is more complex than this, there are a number of algorithms for
string matching with errors
http://www.nist.gov/dads/HTML/stringMatchwError.html
If the equivalents are always character-for-character, it is the
slightly simpler string matching with mismatches.
-paul-
-- Paul E. Black (p.black@acm.org)
- Next message: Randy: "Re: hard disk faster than main memory?"
- Previous message: Thad Smith: "Re: need an algo for string sorting"
- In reply to: Raghavendra Mahuli: "need an algo for string sorting"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
