Parsing GPS data with Bash

Last time we looked at how to get the data to the GPS and now we will have a look at how to parse the data. Turns out that except for the check-sum, everything is pretty straight forward, even in Bash.

So, why bash in the first place? Well, there’s not real reason except that for the something else I’m working on, it’s the ideal glue-code language, allowing me to invoke simply other programs that I do not want to re-code (or take parts of) to do what I want. I must say that I even have a C# version of the GPS data grabber, but while fancier, it does not bring much more than the Bash version.

Reading GPS data with Bash

I am presently working on something that requires geolocation. Not knowing much about GPSes and related topics, I decided to get a USB GPS. This week, let’s have a look at how we can extract information from the USB GPS using Bash.

The first step is to locate your USB GPS as a device. If it’s NMEA compliant, it should mount automagically as a USB serial port. You would think that lsusb -v would show you the device, but it does not always. Sometimes it shows as “Brand X GPS”, sometimes it only shows as a generic device, say “MediaTek Inc.”, or even as a modem. It will typically show up as /dev/ttyUSB0 or /dev/ttyACM0.

Building a Tree from a List in Linear Time (II)

Quite a while ago, I proposed a linear time algorithm to construct trees from sorted lists. The algorithm relied on the segregation of data and internal nodes. This meant that for a list of data items, nodes were allocated (but only contained data; the others just contained pointers.

While segregating structure and data makes sense in some cases (say, the index resides in memory but the leaves/data reside on disk), I found the solution somewhat unsatisfactory (but not unacceptable). So I gave the problem a little more thinking and I arrived at an algorithm that produces a tree with optimal average depth, with data in every node, in linear time and using at most extra memory.

Shallow Constitude

In programming languages, there are constructs that are of little pragmatic importance (that is, they do not really affect how code behaves or what code is generated by the compiler) but are of great “social” importance as they instruct the programmer as to what contract the code complies to.

One of those constructs in C++ is the const (and other access modifiers) that explicitly states to the programmer that this function argument will be treated as read-only, and that it’s safe to pass your data to it, it won’t be modified. But is it all but security theater?

Python Memory Management (Part II)

Last week we had a look at how much memory basic Python objects use. This week, we will discuss how Python manages its memory internally, and why it goes wrong if you’re not careful.

To speed-up memory allocation (and reuse) Python uses a number of lists for small objects. Each list will contain objects of similar size: there will be a list for objects 1 to 8 bytes in size, one for 9 to 16, etc. When a small object needs to be created, either we reuse a free block in the list, or we allocate a new one.

Stemming

A few weeks ago, I went to Québec Ouvert Hackathon 3.3, and I was most interested by Michael Mulley’s Open Parliament. One possible addition to the project is to use cross-referencing of entries based not only on the parliament-supplied subject tags but also on the content of the text itself.

One possibility is to learn embeddings on bags of words but on stemmed words to reduce the dimensionality of the one-hot vector, essentially a bitmap where the bit corresponding to a word is set to 1 if it appears in the bag of words. So, let us start at the beginning, stemming.

Fast Interpolation (Interpolation, part V)

In the last four installments of this series, we have seen linear interpolation, cubic interpolation, Hermite splines, and lastly cardinal splines.

In this installment (which should be the last of the series; at least for a while), let us have a look at how we can implement these interpolation efficient.

Cardinal Splines (Interpolation, part IV)

In the last installment of this series, we left off Hermite splines asking how we should choose the derivatives at end points so that patches line up nicely, in a visually (or any other context-specific criterion) pleasing way.

Cardinal splines solve part of this problem quite elegantly. I say part of the problem because they address only the problem of the first derivative, ensuring that the curve resulting from neighboring patches are -continuous, that is, the patches line up at the same point, and are -continuous, that is, the first derivatives line up as well. We can imagine splines what are (up to) -continuous, that is, patches lining up, and up to the -th derivatives lining up as well.

Hermite Splines (Interpolation, part III)

In previous posts, we discussed linear and cubic interpolation. So let us continue where we left the last entry: Cubic interpolation does not guaranty that neighboring patches join with the same derivative and that may introduce unwanted artifacts.

Well, the importance of those artifacts may vary; but we seem to be rather sensitive to curves that change too abruptly, or in unexpected ways. One way to ensure that cubic patches meet gracefully is to add the constraints that the derivative should be equal on both side of a joint. Hermite splines do just that.

Cubic Interpolation (Interpolation, part II)

In a previous entry, we had a look at linear interpolation and concluded that we should prefer some kind of smooth interpolation, maybe a polynomial.

However, we must use a polynomial of sufficient degree so that neighboring patches do not exhibit very different slopes on either side of known points. This pretty much rules out quadratic polynomials, because polynomials of the form are only capable of expressing (strictly) convex (or concave) patches. A quadratic piece-wise function would look something like: