Solved

scan a dictionary for a certain pattern

Posted on 2001-08-22
8
239 Views
Last Modified: 2010-04-06
What is the best/easiest way for scanning a dictionary when given a certain pattern - a pattern like "ABCD" should result in a list of words like  'meat' 'fear' 'word', where a pattern like "ABAB" should result in a list of words like 'haha' 'hoho' and so on...  All help on pattern matching is very welcome.
Best regards,
Daniel
0
Comment
Question by:KinnaerD
8 Comments
 
LVL 4

Expert Comment

by:jsweby
ID: 6412451
I'm not sure about pattern matching ABCD to find any words with A,B,C or D in them, but to find a single word anywhere you can use SQL with wildcards:

SELECT Word FROM Dictionary
WHERE Word LIKE '*a*'
OR Word LIKE '*A*'

This will give you any word with a capital or lowercase A in it at any position. You can reiterate this for all the letters to search for.

J.
0
 

Author Comment

by:KinnaerD
ID: 6412573
Hi J,

This ABC-thing is the pattern which a word follows. For example, the pattern for 'there' is 'ABCDC'.  Another word that matches this pattern is 'where'.  The idea is to use a dictionary (a very long list of words) which is scanned with a given pattern (like this ABCDC) and which returns the words that fit the given pattern here 'there', 'where' ...)

regards,
Daniel
0
 
LVL 11

Expert Comment

by:robert_marquardt
ID: 6412673
As long as you use no '*' wildcard in your pattern the length of the pattern and the length of candidates must be the same.
Apart from that you will have to check all words (assuming that the words are sorted alphabetically).

The match itself is a very interesting one.
If the above pattern description is complete then it describes only equal vs unequal positional char matches.
So transform the pattern in a list of compares.

ABAB transforms to
1<>2
1= 3
1<>4
2<>3
2= 4
3<>4
This list contains unneeded compares.
Optimize it if you encounter speed problems.

Add new <> compares by substituting the other position from the = compares. Normalize the
new <> compare by having the smaller position on the left side.
Now remove all <> compares which are not unique.
In the above sample you would get 2<>3 at least twice meaning that it is implied by the other compares.
I hope this optimization is correct.
0
 
LVL 4

Expert Comment

by:DMN
ID: 6412817
//Here is a function... Please note! Pattern is case sensitive, word is case insensitive...
//==================================================
function match(Pattern,Word:string):Boolean;
var
  i:Integer;
  j:Integer;
begin
  Result := False;
  if Length(pattern)<>Length(Word) then  Exit;
  Word := AnsiUpperCase(Word); // Word is case insensitive, Pattern is case sensitive.
  for i:=1 to Length(Pattern) do
    for j:=1 to Length(Pattern) do
      if (Word[j]=Word[i]) xor (Pattern[i]=Pattern[j]) then
          Exit;
  Result := True;
end;
//==================================================
// That's ALL!!! Dmn. :)
//==================================================
// p.s. Nice task. Nice solution. You can even optimize it...
0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 
LVL 4

Accepted Solution

by:
DMN earned 150 total points
ID: 6412820
Oops! I make mistake in previuos comment, in FOR loop by J. It's even shorter :) Here is correct function:

function match(Pattern,Word:string):Boolean;
var
  i:Integer;
  j:Integer;
begin
  Result := False;
  if Length(pattern)<>Length(Word) then  Exit;
  Word := AnsiUpperCase(Word); // Word is case insensitive, Pattern is case sensitive.
  for i:=1 to Length(Pattern) do
    for j:=1 to i-1 do
      if (Word[j]=Word[i]) xor (Pattern[i]=Pattern[j]) then
          Exit;
  Result := True;
end;
0
 
LVL 4

Expert Comment

by:DMN
ID: 6412830
Oop's. I'm so sorry, but "FOR I" has a little mistake too... More faster solution:

function match(Pattern,Word:string):Boolean;
var
  i:Integer;
  j:Integer;
begin
  Result := False;
  if Length(pattern)<>Length(Word) then  Exit;
  Word := AnsiUpperCase(Word); // Word is case insensitive, Pattern is case sensitive.
  for i:=2 to Length(Pattern) do
    for j:=1 to i-1 do
      if (Word[j]=Word[i]) xor (Pattern[i]=Pattern[j]) then
          Exit;
  Result := True;
end;
0
 

Author Comment

by:KinnaerD
ID: 6412958
Hi DMN,

>for i:=2 to Length(Pattern) do
>   for j:=1 to i-1 do
>     if (aWord[j]=aWord[i]) xor (Pattern[i]=Pattern[j]) >then
>         Exit;
> Result := True;

thanks for this wonderful function!  As you see, I changed the variable Word into aWord.  I was fiddling with XOR as well, but your answer is the best.  Thanks.
Daniel
0
 
LVL 4

Expert Comment

by:DMN
ID: 6413005
(aWord[j]=aWord[i]) xor (Pattern[i]=Pattern[j])

is equivalent of:

(aWord[j]<>aWord[i]) and (Pattern[i]=Pattern[j])
                     or
(aWord[j]=aWord[i]) and (Pattern[i]<>Pattern[j])


Good luck!
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Windows Drag & Drop Location 2 85
delphi prevent click fast 2 166
Simple Delphi Question 9 77
Virtuailstring tree compare node issue 14 90
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
Creating an auto free TStringList The TStringList is a basic and frequently used object in Delphi. On many occasions, you may want to create a temporary list, process some items in the list and be done with the list. In such cases, you have to…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now