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


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

Rep: Reputation: 21
Algorithm for binary frequency search


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.


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
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.

Old 07-17-2010, 08:15 AM   #3
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
I've got a bit of an obscure question for you ...

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

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
Originally Posted by akamikeym View Post
Even if anyone knows what type of search algorithm this might be would be a help.

Start from looking up

gliding average
Old 07-17-2010, 11:15 AM   #5
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
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).


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 > Forums > Non-*NIX Forums > Programming

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

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