Welcome to the most active Linux Forum on the web.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org Algorithm for binary frequency search
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 07-16-2010, 09:32 AM #1 akamikeym Member   Registered: May 2008 Posts: 112 Rep: Algorithm for binary frequency search Hi, I've got a bit of an obscure question for you to test your brains a wee bit. I'm trying to implement a search program to find areas of high density in a binary string. E.g. Code: ```[0001001010 0001110001 0000001000 1001000010 0101100100]``` Where density is the number of 1's / number of digits with a maximum number of digits being the current number in a buffer (in this example 50). So for the example the density for the whole buffer is 15/50. But the density of Buffer[14..20]=[1110001]=4/7. So if looking for areas of density = 1/3 it would find the longest sequences of density over 1/3. So in the example. Buffer[4..9]=[100101]=3/6=1/2 which is above 1/3 but it is within the Buffer[4..48]=[100101000011100010000001000100100001001011001]=15/45=1/3 So Buffer[4..48] would be chosen.
 07-16-2010, 09:33 AM #2 akamikeym Member   Registered: May 2008 Posts: 112 Original Poster Rep: Even if anyone knows what type of search algorithm this might be would be a help. Cheers
07-17-2010, 08:15 AM   #3
salasi
Senior Member

Registered: Jul 2007
Location: Directly above centre of the earth, UK
Distribution: SuSE, plus some hopping
Posts: 4,070

Rep:
[QUOTE=akamikeym;4035289
I've got a bit of an obscure question for you ...
[/QUOTE]

You are absolutely right...I read your first post and didn't spot a question anywhere in it.

Quote:
 So Buffer[4..48] would be chosen.
Are you saying:
• you have a predetermined buffer length, and you have no concern that you might get different results with other buffer lengths
• you are happy to ignore any areas of high density which happen to fall at buffer boundaries
• you aren't bothered about anything other than the number of 1s in a particular buffer (0000111000 doesn't count for more than 01000100010, for example).
• you are not interested in, eg, the maximum density, but every occurrence of a density over some some specified value

07-17-2010, 10:55 AM   #4
Sergei Steshenko
Senior Member

Registered: May 2005
Posts: 4,481

Rep:
Quote:
 Originally Posted by akamikeym Even if anyone knows what type of search algorithm this might be would be a help. Cheers
Start from looking up

gliding average
.

 07-17-2010, 11:15 AM #5 PTrenholme Senior Member Contributing Member   Registered: Dec 2004 Location: Olympia, WA, USA Distribution: Fedora, (K)Ubuntu Posts: 4,186 Rep: If you're looking for areas of maximum "density," and you don't specify a minimum buffer length, then it's clear that you maximum density is 1, and it occurs for every buffer of length 1 that contains a 1. I think that you should edit your first post (or start another thread) where you actually define what you mean by a "buffer," "length," "density," and ask a question. Do this before any examples, since you seem to think that we can guess what you actually mean from a few examples. (As you should see by now, examples are open to different interpretation by different people.)
 07-18-2010, 04:59 AM #6 akamikeym Member   Registered: May 2008 Posts: 112 Original Poster Rep: Hi there. Thanks for the help and trying to figure out my rather confused query. I managed to track down the solution which mostly came from a clearer understanding of what the problem was. I was essentially looking for clusters of 1's in my binary string. I initially found and implemented an algorithm called DBSCAN for finding clusters in N dimensional space, but while I was doing this I realised that my situation was much simpler because I was getting my 1-D data in order. Basically all I needed to do was define what the furthest distance between two 1's would be for them to count as a cluster and the minimum number of 1's needed for a cluster (to remove noise).

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post bnixon10 Programming 4 04-05-2008 10:46 PM cyborgt Programming 3 02-21-2008 06:41 PM Zeno McDohl Programming 3 01-27-2008 06:07 PM remissed Programming 3 05-08-2006 12:28 AM Tinkster Programming 6 12-05-2002 07:25 PM

LinuxQuestions.org

All times are GMT -5. The time now is 12:29 AM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -