LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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


Reply
  Search this Thread
Old 07-16-2010, 09:32 AM   #1
akamikeym
Member
 
Registered: May 2008
Posts: 112

Rep: Reputation: 21
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.
 
Old 07-16-2010, 09:33 AM   #2
akamikeym
Member
 
Registered: May 2008
Posts: 112

Original Poster
Rep: Reputation: 21
Even if anyone knows what type of search algorithm this might be would be a help.



Cheers
 
Old 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: Reputation: 896Reputation: 896Reputation: 896Reputation: 896Reputation: 896Reputation: 896Reputation: 896
[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
 
Old 07-17-2010, 10:55 AM   #4
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by akamikeym View Post
Even if anyone knows what type of search algorithm this might be would be a help.



Cheers
Start from looking up

gliding average
.
 
Old 07-17-2010, 11:15 AM   #5
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,186

Rep: Reputation: 347Reputation: 347Reputation: 347Reputation: 347
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.)
 
Old 07-18-2010, 04:59 AM   #6
akamikeym
Member
 
Registered: May 2008
Posts: 112

Original Poster
Rep: Reputation: 21
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).
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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



Similar Threads
Thread Thread Starter Forum Replies Last Post
C Binary Search Tree bnixon10 Programming 4 04-05-2008 10:46 PM
Question about Binary search on mips. cyborgt Programming 3 02-21-2008 06:41 PM
Binary search tree in C Zeno McDohl Programming 3 01-27-2008 06:07 PM
Binary Search Tree in Python remissed Programming 3 05-08-2006 12:28 AM
need *fast* algorithm for binary file search Tinkster Programming 6 12-05-2002 07:25 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

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

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration