We present two novel entropy-based measures that quantify sleep-stage transition dynamics (sleep structure) from polysomnogram derived hypnograms: Walsh spectral entropy (WSE) and Haar spectral entropy (HSE). These measures quantify patterns of temporal regularity of a categorical time series without requiring numerical encoding (scaling) of the (categorical) sleep stages. Additionally, we show that conditional entropy (CE) is well suited for quantifying predictability of the hypnogram. The relationship of those measures with traditional sleep fragmentation indices (arousal index, total sleep time, and sleep efficiency) is explored for a 394 participant sample of the Cleveland Family Study, an epidemiologic study in which standardized single-night polysomnogram data were collected. The new entropy-based sleep structure measures (WSE, HSE, and CE) are positively correlated (moderate to weak) with the traditional sleep fragmentation indices. Because the sleep structure measures developed in this paper provide direct information related to temporal patterns of sleep that is not contained in traditional sleep fragmentation measures, the correlation between these new alternative sleep structure measures and the traditional sleep fragmentation measures is less important. Our goal is not to develop alternative measures that correlate highly with traditional measures of sleep fragmentation, but rather to provide methods to quantify sleep structure by examining other (e.g., dynamic sleep-stage transition) properties of the hypnogram. Additionally, the relationship of the new entropy-based and traditional measures with daytime sleepiness as quantified by the Epworth sleepiness scale (ESS) is investigated. Multiple linear regression analysis shows that WSE has a stronger relationship with ESS than the traditional measures, even after both are adjusted for common confounders (age, race, gender, and body mass index). This further suggests that the entropy-based measures, especially WSE, are capturing additional temporal patterns of sleep not captured in the traditional sleep fragmentation measures, and have a relationship with daytime sleepiness.